How to know the complexity (number of transitions) in the search on the hash table?

0 like 0 dislike
6 views
Please tell me how to calculate the complexity of searching each of the values in Zapadnoi hash table (the number of “transitions”)?

Here is a method search. The algorithm works, but chet always outputs zero or one ( Tell me where is the error?

public int get(String key) { int chet=0; int hash1 = myhash1( key ); int hash2 = myhash2( key ); while (table[hash1] != null && !table[hash1].key.equals(key)) { chet++; hash1 += hash2; hash1 %= TABLE_SIZE; } System.out.println(chet); return table[hash1].value; }
by | 6 views

3 Answers

0 like 0 dislike
And why did you decide that there should be more transitions? Run the program step by step in the debugger, let's see how and what happens.
by
0 like 0 dislike
To write your own hash table, manual and every function ->next() count counters))
The idea is that if memory serves just to take and to calculate the complexity of hespoke in STL is impossible, except to change them(but there may of course be wrong). For they teach all this in the pros.
In Destablize unknown number of collisions.
For example, imagine a phone book
Hassymbol A connection with Artem -> next() -> Alex -> next() -> Anya....
Hassymbol B - connection to bill-> next() -> Bob - next() -> Bronislaw....
Artem knows Alex, but Artem not naet Anya
Bill knows Bob, but bill doesn't know Bronislaw
This principle is the relationship between elements associated with the "hash". Therefore, to calculate the final authority. We should review the whole linked list and poschitat his position in this "at this point," the state of your table. After each izmenenia in the hash, it can vary.

p. S. if there is such "unique" features in Java, it will be interesting to read too. But somnivayus... ))
by
0 like 0 dislike
In the ideal case - O(1) worst O(n). What's the problem?
by

Related questions

0 like 0 dislike
3 answers
0 like 0 dislike
3 answers
0 like 0 dislike
1 answer
110,608 questions
257,186 answers
0 comments
33,912 users