U
U
up72018-05-04 13:09:53
Java
up7, 2018-05-04 13:09:53

How to find out the complexity (number of transitions) in a hash table search?

Tell me, please, how to calculate the complexity of searching for each of the values ​​in the completed hash table (the number of “jumps”)?
Here is the search method. The algorithm itself works, but always outputs chet 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;
    }

Answer the question

In order to leave comments, you need to log in

3 answer(s)
R
Rsa97, 2018-05-04
@Rsa97

And why did you decide that there should be more transitions? Run the program step by step in the debugger, see how and what happens.

T
Therapyx, 2018-05-04
@Therapyx

Write your own hash table, manually and count the counter for each function ->next()))
In theory, if memory serves, it’s impossible to just take and calculate the complexity of hash search in STL, except to edit it (but of course I can be wrong). For he taught all this in pluses.
The hashtable has an unknown number of collisions.
For example, imagine a telephone directory
Hashsymbol A - connection with Artyom -> next() -> Alex -> next() -> Anya....
Hashsymbol B - connection with Bill-> next() -> Borya - next() - > Bronislav....
Artyom knows Alex, but Artyom doesn't find Anya
Bill knows Borya, but Bill doesn't know Bronislav
This principle is the relationship between the elements associated with the "hash". Therefore, to calculate the final instance. It is necessary to go through the entire linked list and post-read its position in the given "at this moment" state of your table. After each change in the hash - it can change.
ps if there are such "unique" functions in Java, then it will be interesting to read it too. But I doubt...

M
MaxLich, 2018-05-04
@MaxLich

In the ideal case - O(1), in the worst case - O(n). What is the problem?

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question