Hash Function 문제 풀이 보고서
Description:
In data structure Hash, hash function is used to convert a string(or any other type) into an integer smaller than hash size and bigger or equal to zero. The objective of designing a hash function is to "hash"the key as unreasonable as possible. A good hash function can avoid collision as less as possible. A widely used hash function algorithm is using a magic number 33, consider any string as a 33 based big integer like follow:
hashcode("abcd") = (ascii(a) * 333 + ascii(b) * 332 + ascii(c) *33 + ascii(d)) % HASH_SIZE
= (97* 333 + 98 * 332 + 99 * 33 +100) % HASH_SIZE
= 3595978 % HASH_SIZE
here HASH_SIZE is the capacity of the hash table (you can assume a hash table is like an array with index 0 ~ HASH_SIZE-1).
Given a string as a key and the size of hash table, return the hash value of this key.f
Example:
For key="abcd"and size=100, return 78
Link:
http://www.lintcode.com/en/problem/hash-function/#
문제 해결 방법:
코드는 간단하지만 int 형식은 넘치기 쉽기 때문에 여기서 두 가지 주의해야 할 점이 있습니다. 1) 1LL * 어떤 수든지 롱롱 데이터 형식으로 전환되어 1회 계산이 넘치지 않도록 합니다. 2) 매번 계산 후%HASH_SIZE, 마지막 패턴 제거 효과와 동일하며 오버플로우를 방지합니다.
Tips:
result는 처음에는 0이기 때문에 매번 33에 대한 것이지char33에 대한 것이 아니라 지수 체감 효과에 도달한다.
Time Complexity：
O(N)
전체 코드:
int hashCode(string key,int HASH_SIZE) { if(key.size() == 0) return 0; int result = 0; int len = key.size() - 1; for(char ch : key) result = (1LL * result * 33 + ch) % HASH_SIZE; return result; }
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
