[자료구조]해시테이블

해시테이블

효율적인 탐색을 위한 자료구조

key를 vaslue에 대응

key : value

구현

연결리스트(linked list)

해시 코드 함수(hash code function)

1. 키의 해시 코드를 계산한다
2. hash(key) % array_length 방식으로 해시코드를 이용해 배열의 인덱스를 구한다
3. 배열의 각 인덱스에는 키와 값으로 이루어진 연결리스트가 있다 충돌을 대비해 연결리스트를 이용

3번째에서 충돌이란 서로 다른 두개의 키가 같은 해시 코드를 가리키거나 서로다른 두 개의 해시 코드가 같은 인덱스를 가리키는 경우