Java – hashcode, implementation and relationship with HashMap

So I asked another related question here: Java string hash function with avalanche effect, but now I have a different related question

The hashcode () function of string I built in that problem has no avalanche effect This means that, for example, if I have the strings "K1", "K2", "K3" and I call hashcode () on each, the returned values will be continuous

Now, based on my memory of data structure 101, my impression is that this is a bad thing Because it is assumed that HashMap selects buckets by algorithm, for example:

class HashMap {
    private int capacity;
    private int chooseBucket(String key) {
        return key.hashCode() % capacity;
    }
}

This means that similar keys are stored in consecutive buckets, resulting in a higher collision rate, from O (1) reducing the query time of large o to... Who knows how bad... May be worse than o (log n)

The answer type I got in the first question was "there is no need for avalanche effect", "it is only used for encrypting hash functions", and "the hashcode of string is fast and suitable for small hash mapping"

This puzzles me When they are small, all data structures are fast Will sun provide a default hashcode function for large datasets? At that time, the performance of HashMap was really important, wasn't it?

Or, what did I miss? Please give me your advice

Solution

Storing keys in contiguous stores does not result in performance degradation Store the key in the same bucket (for example, chaining) When using links to resolve hash conflicts:

>Worst case: each hash value is the same, so all elements are in the same bucket. In this case, you get o (n) performance (assuming that the chain is a linked list) > best case: each hash value is different, so each element ends up in a different bucket, so you can get the expected o (1) performance

Hash codes for hash lists (and so on) do not require avalanche effect