[Data Structure] Hash Table

🌼 Hash Table?

해시 테이블은 해시 함수를 통해 key-value 형태의 데이터가 저장된 자료구조이다. 해시 테이블은 검색하고자 하는 키(Key) 값을 입력 받아서 해시 함수를 실행시키고 이를 통해 반환받은 해시 코드를 배열의 인덱스로 환산해서 데이터(Value)에 접근할 수 있다. (Java Script의 object, Python의 dictionary, etc.)

🌼 시간 복잡도

아래의 데이터 구조에서 burger의 가격을 알고싶은 경우, 1) 배열 형태에서는 첫번째로 menu인 burger를 찾아 price를 확인할 수 있다. 즉 시간 복잡도는 O(n)이며 이는 배열이 길면 길어질수록 찾는 시간도 오래걸리게 된다. 2) 반면에 해시 테이블 구조의 경우, burger라는 key값으로 price라는 value를 바로 확인할 수 있기때문에 시간 복잡도가 O(1)이다. 또한, 아이템을 삭제하거나 추가할때도 시간 복잡도는 O(1)이다.

const menuArray = [
  { name: 'coffee', price: 10 },
  { name: 'burger', price: 15 },
];

const menuObject = {
  coffee: 10,
  burger: 15,
}

🌼 Load Factor

해시 테이블에 원소가 차 있는 비율은 테이블의 성능에 영향을 미친다. 해시 테이블의 크기가 m이고, 저장된 원소의 총 갯수가 n이면 적재율은 n/m으로 나타내고 이를 ⍺로 표기한다.

🌼 Collision

각기 다른 key에 대해서 해시함수가 동일한 숫자를 준 경우를 collision(충돌)이 발생했다고 한다. 해시 알고리즘을 잘 작성하지 않으면 특정 위치에 데이터가 여러개 적재되게 되고 그 결과로 충돌이 발생되게 되면 시간 복잡도가 O(1) -> O(n)까지 늘어날 수도 있다.

• key는 무한하지만 해시 알고리즘으로 반환된 해시 코드는 유한하다.
• 만약, 반환된 해시 코드가 전부 다르더라도 제한된 메모리로 인덱스가 동일할 수 있다.

위와 같은 조건으로 충돌은 언제든지 발생할 수 있으며 이런 충돌을 잘 처리할 수 있도록 해시 알고리즘을 짜는 것이 중요하다.

출처:YOUTUBE-노마드코더, 쉽게 배우는 알고리즘