Hash-Table

@TODO

---

Hash
Hash Table

해쉬 함수와 함께 데이터 검색을 효율적으로 하기 위해 사용되는 구조

Key(데이터 식별자), Value(데이터의 내용)이 한 쌍을 이루는 데이터를 저장

특정 데이터가 몇 번째에 저장돼 있는지 모르므로 앞에서부터 차례대로 확인?
선형 탐색
데이터양에 비례해서 계산 시간이 늘어남
배열 탐색에 시간이 걸리므로 탐색에는 적합하지 않은 구조

So,

1. 데이터를 추가할 때 해시함수를 이용해서, Key에 해당하는 해시값을 계산
   • i.e. Joe -> 4928
2. 구한 해시값을 해시 테이블의 크기로 나머지 연산 (mod 연산)
   • i.e. 4928 % 5 = 3
3. 계산한 값 위치에 데이터 저장
   • i.e. 3번 위치에 저장
4. 반복, 만약 중복된 값이 나오면 (충돌이라고 함) 연결리스트구조로 기존 데이터와 연결 (연쇄법 Chaining이라고 함)
5. 검색 시 마찬가지로 mod 연산 값으로 찾음, 충돌로 인해 연결리스트가 만들어진 위치일 경우, 선형 탐색 실시

해시 함수를 통해 배열 내의 특정 데이터에 빠르게 접근 가능
한편, 해시값이 충돌할 때는 리스트를 이용하고 있어서 저장할 데이터 수가 정해져 있지 않더라도 유연하게 대응할 수 있음

해시테이블의 배열 크기
너무 작으면 충돌이 많아지고 -> 선형 탐색의 빈도가 높아짐
너무 커지면 데이터가 없는 공간이 많아져서 메모리를 낭비

적절한 크기로 설정하는 것이 중요

충돌 처리 방법은 연쇄법 말고도 여러 가지가 있음

개방 주소법 Open addressing
충돌이 발생한 경우 다음 후보가 될 주소 (배열 상의 위치)를 구해서 거기에 저장하는 방식
해당 주소에도 데이터가 존재한다면 다음 후보 주소를 구하며 비어있는 곳을 찾을 때까지 다음번 주소를 구함

다음 주소를 어떻게 구하는 가는
해시 함수를 여러 개 사용한다던지, ‘선형 탐사’ 등 몇 가지 방법이 있음

해시 함수의 경우,
해시값으로부터 원래 값을 추측할 수 없도록 구현하기도 하지만,
보안을 위한 것이므로 필수적인 조건은 아님

데이터의 유연한 저장과 빠른 접근이 가능한 해시 테이블은
프로그래밍 언어의 연관 배열 Associative array등에 사용되고 있음

🫧