HashTable

Hash Table

• key, value로 데이터를 저장하는 자료구조
• 빠르게 검색가능한 자료구조 -> 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문
• 각각의 key값에 대해 해시함수를 적용해 배열의 고유한 index를 생성하고, index를 활용해 값을 저장하거나 검색
• 저장/삭제/조회 -> O(1)

해시 함수

• 임의의 크기를 가진 데이터를 '고정크기'의 값에 대응하게 하는 함수
• 함수이기 때문에 입력값이 같은면 출력값은 항상 같다.
• 입력값이 달라도 출력값이 다를 수 있다.

해시 값

• 어떤 데이터를 해시함수에서 넣어서 나온 결과

해시 충돌

• 입력값이 같은데 출력값이 같은 경우
• 없을 수록 좋다
• 최악의 경우 검색속도 O(n)으로 느려질 수 있다.

1. Seperate Chaining(분리 연결법)

• 같은 공간에 mapping 되면 리스트로 추가 해줌

2. Open Addressing(개방 주소법)

• 충돌이 일어날 경우 색인을 늘려주며 빈공간에 저장

 

• 해시함수로 고정된 크기의 데이터로 변환
• 배열색인에 대응하게 하기위해 %연산