해시는 임의의 크기를 가진 데이터를 고정된 데이터의 크기로 변환시키는 것을 말한다. 이를 이용해 특정한 배열의 인덱스나 위치, 위치를 입력하고자 하는 데이터의 값을 이용해 저장하거나 찾을 수 있다. 기존에 사용했던 자료구조들은 탐색이나 삽입에 선형시간이 걸리기도 했던 것에 비해, 해시를 이용하면 상수시간으로 처리 할 수 있다.
Direct Addressing Table은 key-value 쌍의 데이터를 배열에 저장할 key 값을 직접적으로 배열의 인덱스로 사용하는 방법이다.
Hash Table은 key-value 쌍에서 key 값 테이블에 저장할 때 Direct Addressing Table과 달리 함수를 이용해 key값의 계산을 수행한 후 그 결과값을 배열의 인덱스로 사용하여 저장하는 방식이다. 여기서 key 값을 계산하는 함수는 해쉬 함수(Hash Function)이라고 부르며 해쉬 함수는 입력으로 key를 받아서 배열의크기-1 사이의 값을 출력한다.
해쉬의 첫 정의대로 임의의 숫자를 배열의 크기만큼으로 변환시킨 것이다.
이경우 k 값이 h(k)로 해쉬되었다고 하며 h(k)는 k의 해쉬값이라고 한다.
3. Open Addressing
open Addressing은 key 값을 테이블에 저장하는 Direct Addressing Table과는 다르게 모든 데이터(key+데이터)를 테이블에 저장하는 방법이다. 데이터를 모두 읽어오기 때문에 포일터를 쓸 일이 없어 포인터를 사용함으로써 발생할 수 있는 오버헤드를 방지할 수 있다. 포인터가 필요 없어서 구현이 훨씬 용이해졌으며 포인터 접근에 필요한 시간이 없기 때문에 큰 성능 향상이 있다.
검색하고자하는 key값을 받아서 해쉬함수를 돌려 반환받음 해쉬코드를 배열의 인덱스로 환산해서 데이터에 접근하는 자료구조.
Key → 해쉬함수( 해쉬 알고리즘) → 해쉬코드 → 인덱스로 나눠줌 → Value접근
해시코드를 인덱스로 나눠주는 알고리즘이 필요. 위에서는 hashcode % 3를 씀
이때, 같은 인덱스를 갖는 Value들이 발생한다. (jin, hee, min) 이 value들은 Linkedlist 구조로 연결되어 저장된다.
<aside> 👨💻 hash table : key에 value를 저장하는 데이터구조
</aside>
O(1) 상수시간 이 걸린다.