프로그래밍 언어에서 배열과 해시 테이블의 차이점은 무엇입니까?


대답 1:

해시 테이블은 배열을 사용합니다. 배열에는 해싱에 중요한 속성이 있습니다. 인덱스를 알고 있으면 일정한 시간에 모든 요소에 액세스 할 수 있습니다.

버킷에 배열을 사용할 수 있습니다. 예를 들어, 모스 부호와 같은 것을 디자인하기 위해 텍스트에서 각 문자의 수를 세고 싶다고 가정 해 봅시다. 26 개의 항목으로 배열을 만듭니다 (간단한 로마자 알파벳). 문자를 볼 때마다 색인을 계산하고 배열의 해당 항목으로 이동합니다.

해시 테이블은 임의로 긴 키의 경우이를 확장합니다. 키의 해시를 계산하고 해당 인덱스로 이동하십시오. 문제는 여러 키가 동일한 해시를 가질 때입니다. 이것을 처리하는 다양한 방법이 있으며, 그중 일부는 해시의 목적을 무너 뜨립니다 (그러나 구현하기는 쉽습니다). 그들 중 일부는 적어도 평균적으로 일정한 시간 속성을 유지하지 않습니다.

내가 본 가장 좋은 것은 해시 추가 리해시입니다. 수십 년 전에 메모리가 제공되면 Gonnet과 Munroe는 크기에 관계없이 50 % 부하 계수로 평균 4 건 이상의 액세스 권한을 가지고 있음을 입증했습니다. 해시 테이블. 그러나 소수를 사용해야하기 때문에 구현하기가 까다 롭습니다. 어떻게 든 소수를 찾아야합니다. 다행스럽게도 해시 테이블은 너무 커져서 말도 안됩니다.