[알고리즘] Hash table
1. 해쉬 테이블 해쉬 테이블 또는 해쉬 맵은 key와 value를 갖는 자료 구조이다. 주요 동작은 효율적인 검색(주어진 키(예를 들어, 사람 이름)로 적합한 값을 찾는(전화번호)) 이다. 해쉬 함수를 이용
egloos.zum.com
[Hash Collision]
1. Separate Chaining
- Linked List or Red-Black Tree
2. Open Addressing
- Linear Probing
- Quadratic Probing
- Double Hashing
[Resizing]
◎ 체이닝(Chaining)의 장점
- 연결 리스트만 사용하면 된다. 즉, 복잡한 계산식을 사용할 필요가 개방주소법에 비해 적다.
- 해시테이블이 채워질수록, Lookup 성능저하가 Linear하게 발생한다.
◎ 개방주소법(Open Addressing)의 장점
- 체이닝처럼 포인터가 필요없고, 지정한 메모리 외 추가적인 저장공간도 필요없다.
- 삽입,삭제시 오버헤드가 적다.
- 저장할 데이터가 적을 때 더 유리하다.
https://d2.naver.com/helloworld/831311
'2. Computer Science > 자료구조' 카테고리의 다른 글
| 자료구조 트리(그래프) 종류 (0) | 2022.07.09 |
|---|
댓글