Hash Table 질문
안녕하세요 강사님.
좋은 hash function의 조건에서 해시값이 고르게 분포되게 하는 것을 적어주셨는데, 공간효율성을 최대한 좋게 하기 위해서일까요?
아니면 다른 이유들도 있을까요?
답변 1
1
안녕하세요 재윤님.
good hash function의 목표는 해시값을 고르게 분포되게 하는 것입니다. 그 이유는 공간 효율성도 있겠지만, 가장 중요한 이유는 시간 효율 때문이기도 합니다.
해시값이 고르게 분포되지 않으면 계속 겹치게 됩니다. 즉 충돌 collision이 발생하죠. collision이 발생할때마다 이를 해결해야 하는데, open addressing 방식이든 seperate chaining이든 어떤 방식을 사용하여 이 문제를 해결하든 추가적으로 시간이 소요됩니다.
그래서 좋은 hash function을 통해 최대한 해시값이 충돌하지 않는게 최우선이고, 그럼에도 불구하고 충돌이 발생하면 위의 두 가지 방법(open addressing, seperate chaining)을 통해서 해결하는 것입니다.
질문에 대한 답이 됐을까요!!?
노션 접근이 안됩니다 ㅠㅠ
0
120
2
노션 공유 부탁드립니다.
0
58
2
노션 공유가 안됩니다!
0
152
2
프로세스가 많아질수록 segment table도 많아지는 건가요?
1
73
2
노션 공유가 사라졌습니다.
0
163
2
post 요청
0
56
1
http
0
64
1
mutex, semaphore와 deadllock
0
99
3
실행중인 프로세스는 메모리를 연속적으로? 아니면 불연속적으로 사용하나요?
0
72
1
노션 공유 요청 드립니다.
0
124
1
노션 공유 요청드립니다.
0
87
1
Dynamic Array와 Linked List의 시간복잡도에 대해서..
0
115
1
노션
0
110
1
질문이있습니다 선생님!
0
109
1
질문이있습니다 선생님!
0
99
1
질문이있습니다 선생님!
0
93
1
질문이있습니다 선생님!
0
163
2
질문이있습니다 선생님!
0
152
2
질문이 있습니다 선생님!
1
198
2
질문이 있습니다 선생님!
0
124
1
질문이있습니다 선생님!
0
88
1
질문이 있습니다 선생님!
0
109
1
질문이 있습니다 선생님!
0
91
1
물리적 메모리에 연속적으로 저장하지 않는 이유
0
133
1