辅导HASH FUNCTION、讲解MyHashSet object、辅导Java编程设计、Java讲解
- 首页 >> 其他 WRITING A HASH FUNCTION
Background:
In lecture we discussed hashing and hashing functions. You assignment will be to write you own, completely original, hashing function without any assistance from people or the web. The idea is simple. Design a loop that uses every char in the string to produce an integer that is unique to every string. That integer then determines where the key is stored into an array. Ideally, any 2 strings that are not equals() to each other should hash to a different integer value. In practice this is impossible - at least no one knows a perfect hashing function that does not blow up on even small string lengths. As a result the best we can do is write a function that distributes the keys uniformly over a limited number of integers. An example of an optimal function is a follows: You have 1 million keys to hash, they map to into a range of integers in [1..100,000] and there are exactly 10 words per integer in [1..100,00]. In this case we say the array has 100,000 buckets and each bucket has the same number of keys: 10. The hash function has done the best possible job of distributing K keys into N buckets since each bucket contains K/N keys.
SCRIPT GRADER CURRENTLY USING THE 50 MILLION WORD FILE.
Execute your Tester using this pattern: java HashTester 10000 15 172822Words.txt
The first cmd arg represents the number of buckets.
The second is the ideal bucket size.
The third is the input file of strings.
Depending on the numbers you enter, the tester may not read all the keys from the file.
In the above sample execution the tester defines a MyHashSet object then calls .add() 10000 x 15 times. The hash set object does not actually store the keys, it just increments the counters for each bucket. After the hashing is done, some stats are printed which indicate how evenly the keys were distributed among the buckets.
Background:
In lecture we discussed hashing and hashing functions. You assignment will be to write you own, completely original, hashing function without any assistance from people or the web. The idea is simple. Design a loop that uses every char in the string to produce an integer that is unique to every string. That integer then determines where the key is stored into an array. Ideally, any 2 strings that are not equals() to each other should hash to a different integer value. In practice this is impossible - at least no one knows a perfect hashing function that does not blow up on even small string lengths. As a result the best we can do is write a function that distributes the keys uniformly over a limited number of integers. An example of an optimal function is a follows: You have 1 million keys to hash, they map to into a range of integers in [1..100,000] and there are exactly 10 words per integer in [1..100,00]. In this case we say the array has 100,000 buckets and each bucket has the same number of keys: 10. The hash function has done the best possible job of distributing K keys into N buckets since each bucket contains K/N keys.
SCRIPT GRADER CURRENTLY USING THE 50 MILLION WORD FILE.
Execute your Tester using this pattern: java HashTester 10000 15 172822Words.txt
The first cmd arg represents the number of buckets.
The second is the ideal bucket size.
The third is the input file of strings.
Depending on the numbers you enter, the tester may not read all the keys from the file.
In the above sample execution the tester defines a MyHashSet object then calls .add() 10000 x 15 times. The hash set object does not actually store the keys, it just increments the counters for each bucket. After the hashing is done, some stats are printed which indicate how evenly the keys were distributed among the buckets.