헤시 맵은 파이썬의 딕셔너리를 생각하면 된다.
Key와 Value로 이루어져 있으며 값에 대한 접근, 삽입, 삭제 등이 O(1)로 매우 빠르다는 장점이 있다.
해시 맵의 원리
1. Key값을 입력으로 받아 해시를 출력하는 해시함수를 돌리게 된다.
2. 해당 해시에 값을 저장한다.
3. 해시가 충돌하면(서로다른 Key가 동일한 해시를 출력) 개별 체이닝 or 오픈 어드레스 방식으로 해결한다.
3-1 개별 체이닝: 해시가 충돌하면 값의 뒷 부분에 Linked List를 이용해 값을 붙인다. (이 경우 키 값은 다르니 매칭되는 key를 찾아 return하면 된다)
3-2 오픈 어드레스: 해시가 충돌하면 비어있는 다른 해시에 값을 저장한다. (파이썬의 딕셔너리는 이 방식)
4. 공간의 3/4(java)이 채워지면 새로운 공간을 할당 한다.
3번은 해당 링크 참고
https://ojy9612.tistory.com/20
랜덤 값 충돌
랜덤 값을 1~100 으로 100명에게 하나씩 주어진다. 이때 동일한 값을 가질 확률은 6.3% 일때 50%, 15.6% 일때 99%에 해당한다. 전체의 6.3% 즉 7명의 수를 비교했을 때 동일한 값을 가질 확률은 50%, 15.6%인 1
ojy9612.tistory.com
'CS' 카테고리의 다른 글
| 쓰레드 특징 (프로세스와 비교) (1) | 2024.01.12 |
|---|---|
| ORM, JPA, Spring Data JPA 란 (0) | 2022.06.09 |
| DB Index (0) | 2022.05.27 |
| REST API (0) | 2022.05.22 |
| 랜덤 값 충돌 (0) | 2022.05.18 |