Hashing
Feb 19, 2024
도입배경 : linked list에서의 map performance는 삽입할때는 O(1)이지만, 삭제와 검색할때 O(n)이 소요되고 Direct-address table을 구성하면 모든 operation이 O(1)이지만 실제로 key value에 비해서 사용되지 않는 key가 많아지는 단점이 존재. => 모든 operation에 O(1)이면서 memory를 아끼는 방법? Hashing
- Division methods : a^b 는 나쁘다. 값이 몰릴 가능성이 높음. 반대로 소수를 채택하면 uniform distribution을 만드는데 도움을 준다.
- Collision Resolution : collision이 발생했을때 이를 막는 방법.
- Open addressing : 충돌이 일어났을때 다음 슬롯을 찾는 방식.
2–1) linear probing : 충돌이 발생하면 충돌 위치로부터 선형적으로 다음 위치를 탐색. chaining 보다 memory는 적게 사용하지만, 수행시간이 오래걸림.
2–2) Quadratic probing : linear probing보다 잘 동작한다. 선형적이 아니라 1,4,9 등 이차식으로 증가하는 거리를 탐색.
2–3) double hashing : 두번째 해시 함수를 사용하여 충돌이 발생했을때 탐색할 위치의 간격을 결정.
