"유명한 검색 회사에서"이 사람의 인터뷰에 대해 읽었습니다.해시 함수 출력을 버킷 수보다 제한해야합니까?
http://asserttrue.blogspot.com/2009/05/one-of-toughest-job-interview-questions.html
그는 해시 테이블을 구현하는 그에게지도 한 질문을했다.
HASH = INITIAL_VALUE;
FOR EACH (CHAR IN WORD) {
HASH *= MAGIC_NUMBER
HASH ^= CHAR
HASH %= BOUNDS
}
RETURN HASH
내가 해시 테이블 배열 길이가 소수해야한다고 설명하고, 경계 번호가 테이블 길이 테이블 길이, 하지만 서로 소 미만 : 그는 다음 말했다.
왜 BOUNDS 숫자가 버킷 개수보다 작아야합니까? 테이블 길이에 비례하는 것은 무엇입니까? 그 멍청한 놈들과 교미가 안되니?
나는 그가 완전히 틀릴 위험이 있습니다. BOUNDS는 버킷 수이거나 마지막 몇 개의 버킷은 사용되지 않을 것입니다.
또한, 버킷 수에 대한 출력의 경계는 해시 함수 외부에 있어야합니다. 이것은 특정 해시 테이블의 구현 세부 사항입니다. 버킷을 많이 사용하는 매우 큰 테이블과 소수를 사용하는 테이블이있을 수 있습니다. 두 문자열 모두 동일한 문자열 -> 해시 함수를 공유해야합니다.
또한 링크 된 페이지를 읽으면 매우 흥미 롭습니다. 나는 그의 해시 테이블을 10,000 버킷과 같은 것으로 구현했을 것입니다. 그것을 읽지 않은 사람들을 위해,이 기사는 1,000,000 개 정도의 단어를 저장하기 위해 4,000,000,000 개의 버킷을 제안합니다. 충돌의 경우 각 버킷에는 단어 구조의 벡터가 있으며 각 단어에는 개수, 일반 텍스트 문자열 및 해시 (버킷 내에서 고유)가 포함됩니다. 이렇게하면 작업량이 훨씬 적기 때문에 메모리를 훨씬 적게 사용하고 현대 캐시로 더 잘 작동합니다.
메모리 사용을 더욱 줄이려면 입력 단계에서 현재 카운트를 기준으로 상위 100,000 미만인 것처럼 해시에서 단어를 도려내기를 실험 할 수 있습니다.
한 번은 잘 알려진 검색 회사에서 취업 인터뷰를했습니다. 나는 똑같은 질문을 가지고있다. 해시 테이블을 사용하여 문제를 해결하려고했습니다.
내가 그 인터뷰에서 배웠던 한 가지는 잘 알려진 검색 회사에서 해결책으로 해시를 제안하지 않았다는 것입니다. 당신은 나무 같은 구조를 사용하지만 항상 해시 테이블이 아닌 정렬 된 구조를 사용합니다.
더 설명해 주시겠습니까? – Unknown
간단한 명시 적 접미사 트리는 똑같은 일을하기 위해 500k 메모리 (중간 구현이 효율적이며 4 바이트 문자 인코딩과 비교적 긴 영어 단어 만 사용)를 사용합니다.
나는 기사에서 그 사람이 자신을 능숙하게 생각한다고 생각한다.
톰에게 감사드립니다. 나는 그가 틀렸다는 느낌을 받았지만 StackOverflow에 지식이 부족한 사람이 아닌지 확실히해야만했습니다. – Unknown
"BOUNDS는 버킷 수 또는 마지막 몇 개의 버킷이 불충분합니다"라고 해시 테이블의 크기를 조정해야 할 때 특별한 트릭 일 수 있다고 생각합니까? – Unknown
나는 % BOUNDS가 완전히 자리를 비 웠음을 완전히 동의합니다. 주어진 입력의 해시는 해쉬가 사용되는 것의 * independent *이어야합니다. 그것을 테이블에 키로 사용할 수 있고, 활에 묶을 수 있으며 \ dev \ null로 파이프 할 수 있습니다. 해시 함수는 무절제해야합니다. – leoger