동적 배열을 사용하여 해시 테이블의 충돌을 처리합니다.

Question

해시 테이블 구현 중 일부를 살펴보면 별도의 연결이 연결된 목록 또는 트리를 통해 처리되는 것으로 보입니다. 동적 배열이 사용되지 않는 이유가 있습니까? 동적 배열을 사용하면 캐시 성능이 향상된다고 생각합니다. 그러나, 그런 구현을 보지 못했기 때문에 나는 아마 뭔가를 놓쳤습니다.

무엇이 누락 되었습니까?

Answer 1

동적 배열을 통해 연결된 목록의 장점 중 하나는 재 해싱을보다 신속하게 완료 할 수 있다는 것입니다. 새로운 동적 배열을 만들고 이전 동적 배열의 모든 요소를 ​​새 배열로 복사하지 않고도 할당을 수행하지 않고도 연결된 목록의 요소를 새 버킷에 재배포 할 수 있습니다.

또한 부하 계수가 작은 경우 연결된 목록을 사용하는 경우의 공간 오버 헤드가 동적 배열의 공간 오버 헤드보다 클 수 있습니다. 동적 배열을 사용할 때는 일반적으로 포인터, 길이 및 용량을 저장해야합니다. 즉, 빈 동적 배열이 있으면 두 개의 정수와 포인터, 요소를 보유하기 위해 미리 할당 된 공간에 대한 공간이 필요합니다. 빈 버킷에서이 공간 오버 헤드는 연결된 목록에 대한 널 포인터 만 저장하는 것과 비교할 때 커집니다. 반면 버킷에 많은 수의 요소가있는 경우 동적 배열은 공간 효율성이 높아지고 참조의 지역성으로 인해 성능이 향상됩니다.

희망이 도움이됩니다.

Answer 2

내가 생각할 수있는 장점 중 하나는 삭제입니다. 반면에 해시의 머리 부분에서 추가 작업이 수행됩니다. 해시에서 값을 삭제하려면 배열에 포함 된 값이 삭제되기를 원할 것입니다. 배열의 중간.