1

As a homework problem, I'm trying to create an implementation of a hashmap using an array. I'm using .hashCode() to create the hash, and I need to find a way to resolve collisions.

I thought of using double hashing, but I can't find a way to do that in Java. I've also tried searching on SO, but most of the questions are discussing how collision resolution is handled etc, rather than how to implement a solution. Would anyone be able to point me to any simple alternatives if there isn't a library to perform double hashing?

EnterPassword
  • 580
  • 1
  • 6
  • 22
  • Sounds like the [XY problem](http://xyproblem.info/). You don't provide enough information to help understand why is it that you have a lot of collisions: maybe the size of the array is too small? Maybe you are using a load-factor which is too small? maybe your objects override hashCode in a bad way? and etc... – Nir Alfasi Sep 25 '19 at 22:03
  • It's not so much that I'm having a lot of collisions, part of the assignment is to create a way to handle collisions if it happens. I'm using an array that is 1.3 times the size of the input array. – EnterPassword Sep 25 '19 at 22:08
  • The JDK uses a binary tree when the keys of a `HashMap` collide if the keys implement `Comparable`. – Johannes Kuhn Sep 25 '19 at 22:13
  • Related: https://stackoverflow.com/questions/2556142/chained-hash-tables-vs-open-addressed-hash-tables –  Sep 25 '19 at 22:37

1 Answers1

1

Double hashing is probably what you'll want to do in production-code, but for a class exercise this is probably an overkill.

What you should do instead, is implement a linked-list attached to each bucket of the hashmap, and when you have a "collision" (meaning, more than one object is mapped to the same key in the array) you just add another link to the list with the new object. A good illustration can be found here.

A nice explanation along with visual graphs that demonstrate this solution can be found here: https://www.geeksforgeeks.org/internal-working-of-hashmap-java/

You might also find the following SO question + answers relevant: What exactly is bucket in hashmap?

Nir Alfasi
  • 53,191
  • 11
  • 86
  • 129