해시의 충돌 및 충돌 회피 방법
기초지식키들의 전체 집합을 U라고 했을 때, 실제로 저장되는 키들의 집합은 K라고 하고 이 K는 U에 비해 상대적으로 작다. 실제 저장되는 K집합이 U에 비해 상대적으로 작기 때문에 해시테이블 T를 위해서 할당된 대부분의 공간이 낭비될 수 있다. 그래서 이렇게 사전에 저장된 키들의 집합 K가 모든 가능한 키들의 전체 집합 U에 비해 훨씬 작을 때 해시 테이블은 직접 주소 테이블보다 훨씬 작은 공간을 필요로 한다. 이때 해시 테이블의 크기를 m이라고 하고 일반적으로 |U|보다 훨씬 작다. 해싱을 이용한 방법에서는 키 k를 갖는 원소는 위치h(k)에 저장된다. 즉 키로부터 저장될 위치를 계산하기 위해 해시 함수 h를 사용한다. 여기서 h는 키들의 전체 집합 U를 해시 테이블 T[0..m-1]의 각 위치에 대..
DataStructure/Algorithms
2016. 9. 4. 02:05
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- linux
- webserver
- log
- Spring
- object
- lood
- java
- NGINX
- logback
- Apache
- async
- TaskExecutor
- JVM
- good practice
- logging facade
- runtime data areas
- slf4j
- log level
- logging
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | ||||
4 | 5 | 6 | 7 | 8 | 9 | 10 |
11 | 12 | 13 | 14 | 15 | 16 | 17 |
18 | 19 | 20 | 21 | 22 | 23 | 24 |
25 | 26 | 27 | 28 | 29 | 30 |
글 보관함