[심화] 해시

개념

해시 함수

임의의 길이를 갖는 데이터를 고정 길이 데이터로 변환하는 함수
데이터를 매핑하는 함수
단방향 함수

• key -> 해시 함수 -> value (hashcode)
• mapping: (key, value)

해시코드 HashCode

어떤 데이터에 해시 함수를 적용한 값
같은 key에 대해서는 동일한 hashcode가 보장됨

해시 테이블 Hash Table

key를 이용해 value에 접근할 수 있는 자료구조
해시 테이블은 버켓으로 구성되어있음
버켓은 슬롯으로 구성되어있음

• hash table > bucket >= slot

특징

빠른 데이터 저장 속도
빠른 검색 속도
많은 메모리 필요
충돌 문제

해시 충돌

서로 다른 key가 같은 value를 가지는 경우
서로 다른 key에 대한 해시 함수 결과가 같은 버켓을 가리켜는 경우
버켓에 데이터가 담길 때 빈 슬롯이 없다면 오버플로우 발생 가능
해시 테이블의 성능 저하 야기

---

활용

자바의 해시

HashSet
HashMap