23/11/25 TIL __ array hash 자료구조란 어떤걸까?

 

 

 

오늘은 hash와 array 라는 자료구조에 대해 적어보겠다.

 

 

🏞️   array

• 메모리의 연속적인 공간에 데이터를 저장
• 인덱스를 통한 접근을 하며, 인덱스를 안다면 데이터를 찾는게 매우 빠르다.
• 한번 생성된 배열의 크기를 변경할 수 없다. 크기가 고정되어 있기 때문이다.
• JavaScript의 `push()` 같은 메소드를 사용하여 배열에 요소를 추가할 때, 배열의 크기가 부족하면 새로운 배열을 생성하고 기존의 요소를 새 배열로 복사한 후, 새로운 요소를 추가한다. 이러한 과정은 내부적으로 일어나는 것이므로 개발자가 직접 인지하기 어렵다고 한다.
• 특정 값을 찾기 위해서 처음부처 차례대로 검색하기 때문에 속도를 O(n)으로 본다.

 

 

 

🚗   hash

• 키와 값을 한 쌍으로 데이터를 저장한다.
• 키를 입력하면 해시함수를 통해 계산된 해시코드가 출력되고, 이 해시코드를 인덱스로 사용해서 데이터를 저장하거나 찾는다.
• 해시 코드는 보통 숫자로 되어 있으며, 특정 길이로 고정되어 있다.
• 해시 테이블은 이 해시 코드를 인덱스로 사용하여 데이터를 저장하고 검색
• 해시 함수는 'apple'을 입력받아서 예를 들면 '123'이라는 해시 코드를 출력했다고 가정하자. 그럼 이 '123'이라는 해시 코드를 인덱스로 사용해서 'apple'에 대한 데이터를 해시 테이블의 123번 위치에 저장한다.
•  이후에 'apple'에 대한 데이터를 찾으려면, 다시 'apple'을 해시 함수에 넣어서 해시 코드를 계산하고, 그 해시 코드를 인덱스로 해서 해시 테이블에서 데이터를 찾으면 되는 구조다. 이런 방식으로 해시 테이블은 매우 빠른 속도로 데이터를 저장하고 검색할 수 있다.
• 하지만 해시 함수는 다른 입력에 대해서도 같은 해시 코드를 출력할 수 있다. 이럴 때는 '충돌'이 발생했다고 말하며, 이 충돌을 해결하기 위한 여러 가지 방법이 있다. 가장 일반적인 방법은 같은 해시 코드를 가진 데이터를 링크드 리스트로 관리하는 것

 

 

항상 자주 나오는 용어라 궁금했는데, 알아보고 나니 이해가 간다. 

아직은 대용량의 데이터를 처리할 일이 없지만, 회사에 들어가면 이런 부분들을 생각하고 처리해야 할 것 같다.