[CE] Hashing

Hashing

• 많은 메모리를 사용(indexing으로)하는 댓가로 검색에 필요한 계산 시간을 단축시키는 검색기법 또는 해당 검색기법이 가능하도록 자료구조를 만드는 방법
• 적절한 hash function과 collision 해결방안을 사용할 경우,
  • $n$개의 요소로 구성된 hash table에서
  • $n$과 무관하게
  • $O(1)$이라는 상수 시간에 데이터를 삽입,삭제, 검색 이 가능.
• 이는 hash function, $h(x)$를 사용하여 해당 함수에 검색 key 값을 입력하면 hash table에서 해당 데이터가 있는 address(주소값)을 얻어내어 random access가 가능함을 의미.

14가 추가될 경우, 주소가 1인 곳에 할당되어 27과 collision이 발생: hashing에서 collision을 완벽히 피할 수는 없음.

 

---

Hashing의 조건

일반적 hashing의 경우,

• 계산이 쉽고
• hash table에 자료를 골고루 배치

하는 hash function이 좋은 hashing function임.

---

Matching에 사용되는 Hashing

matching에서 사용되는 locality sensitive hashing에서는 추가적으로

• 위치가 가까운 vector들은 비슷한 값을 반환하는 hash function이 좋은 hashing function이 됨 (일반적인 hashing과는 정반대)
• → 즉, 가까운 vector들은 collision이 일어나야함.

또한, matching에서 검색키가 위의 예의 scalar 대신 real number vector임.