Until now, I know that after rehashing in a HashMap, all the entries are rehashed with the new table length. But I want to know what will happen when I have collisions.
e.g.
Map<String, String> map = new HashMap<>(5);
map.put("a", "ape");
map.put("b", "bird");
map.put("c", "chicken");
Suppose they have different hashcodes, but "b" and "c" are stored in the same bucket after the internal hashing.
Now I'll insert a fourth entry to reach the load factor therefore rehashing the table:
map.put("d", "dynamite");
Could the entries with collisions be stored in separate buckets or they always will be together (in reverse order according of what I've read)?.
I suppose that the answer to the title is no, because I will get the same internal hashing for "b" and "c", but I'm not sure.
There are two ways you can view collisions here.
One is two objects returning the same value from hashCode() method. In this case, they will end up in the same bucket no matter what size the hashtable array is.
The other case is when two objects have different hash codes but end up in the same bucket due to the array size being less than the 232 unique values that hashCode() can in theory return. Usually, the raw hash code value will be taken modulo array size and that is used to find the right bucket for an entry. Suppose the initial array size is 16 and you have object A with hash code 3 and object B with hash code 19. Since 19 % 16 == 3, object A and object B will end up in the same bucket. If you now resize the array to 18, object A will end up in bucket 3 % 20 == 3 but object B will end up in bucket 19 % 20 == 19. So now they are in different buckets which answers the question posed in the title with a "yes".