Hash Table

hash table은 키, 값으로 구성된 쌍을 저장하고 있는 자료 구조이다.

해시 테이블은 키를 저장할 때에 메모리 공간을 덜 사용할 수 있도록,

키를 해시 함수를 통해 특정 숫자 값의 인덱스로 변환하여 사용한다.

해시 테이블은 필요할 때에만 메모리 크기를 늘리고, 가능한 작은 크기를 유지한다.

이처럼 key값을 해시 함수로 특정 숫자 값으로 변환시켜 저장하는 구조이다.

key값을 해시 값으로 변환하는 과정을 해싱(hashing)이라 한다.

hash table은 storage 배열 안에 hash값을 index로 하는 bucket의 형태로 되어 있다.

이때 bucket안에 원래의 데이터 key, value가 tuple에 들어가 있는 것을 볼 수 있다.

값의 변경을 막기 위해 tuple을 사용하여 bucket에 저장한다.

하지만 여기서 문제가 발생할 수 있다.

해싱을 통해 나온 해시값이 같다면 같은 이미 bucket에 값이 존재해 충돌이 발생할 수 있다.

해시 충돌

이를 해결하기 위해 두 가지 방법이 있다.

1. 체이닝(chaining)

bucket을 연결 리스트나 트리 등으로로 구성하고 해시값이 같아 충돌이 발생하면

해당 bucket에 추가하는 방식으로 해시 충돌을 해결한다.

2. 개방 주소

개방 주소 방법은 해시 충돌 발생 시 다른 bucket에 저장하는 것이다.

이에는 세 가지 방법이 있는데

해시 충돌 시 바로 다음 bucket에 저장하는 선형 탐색법,

해시 충돌 시 보폭을 이차함수를 통해 넓혀가며 저장하는 이차원 탐색법,

해시 충돌 시 다른 해시 함수를 이용해 한 번 더 적용하여 저장하는 이중 해시 법이 있다.

해시 메서드

hash table의 메서드에는 insert, remove, retrieve,_resize가 있다.

let hash = new HashTable();
hash.insert('Lee', 'yuchang') // key 값을 해싱하여 storage에 저장
hash.retrieve('Lee') // 해싱 하여 그 index로 가서 값을 불러옴 -> yuchang
hash.remove('Lee') // 해싱하여 그 index에 해당하는 bucket을 지움

_resize(BucketNum)
// 정보의 개수에 따라 BucketNum을 제어 한다. 
// 메모리의 효율적 사용을 위해 늘리고 줄이기위함(25%down, 75%up)
// resize함수는 따로 실행하지 않고 insert,remove함수 실행시 실행된다.

시간 복잡도