Geek asks and answers

Search for collisions in a hash table

I was looking through the final exam on my data structures, and last year I came across a question. Working on it over the past three hours, I still could not figure out how to solve it, with the exception of trial and error. Here's the question:

"Suppose the size of your hash table is 31, the constant g is also 31, and you use the following hash code

int hash = 0;
int n = s.length();
for (int i = 0; i < n; i++)
   hash = g * hash + s.charAt(i);

and that a separate chain is used to resolve conflicts. List five different names that will contain the hash in the same place in the table. "

I think that to solve this problem there should be some tricks, possibly related to the modulo operator, given the size of the hash table 31, which coincides with the constant g. Sorry if I like this, but I am not asking for code or anything else, just some thoughts / tips on this. Any comments are greatly appreciated. Thanks

+5
source share
2 answers

According to the Wikipedia article on the Java string hashing algorithm (which is the same as the algorithm you propose):

, . , "FB" "Ea" -. hashCode() String 31 'a' 'B' 31, 70 × 31 + 66 = 69 × 31 + 97.

+5

java- ("\0"), :

"a"
"\0a"
"\0\0a"
"\0\0\0a"
"\0\0\0\0a"

( ):

> cat Foo.java
class Foo {
    public static void main(String[] args) {                                    
        System.out.println("a".hashCode());                                     
        System.out.println("\0a".hashCode());                                   
        System.out.println("\0a".length());
        System.out.println("\0a".equals("a"));
    }                                                                           
}           
> javac Foo.java                                        
> java Foo                                                       
97
97
2
false

, .

, , , ASCII. :

"\002\000"
"\001\037"

etc. (these are octal triplets - above both hashes 62). but is it easy to deduce five examples (still a hash) for this style?

+6
source

More articles:


All Articles