Welcome to my Java Hash Table tutorial. A Hash Table is a data structure offers fast insertion and searching capabilities. The negative is that they are limited in size because they are based on arrays. They are also hard to order.
People get confused about them because of the Hash Function. A hash function is used to generate a unique key for every item in the array. Since every item is entered using a calculation, this allows you to reverse the calculation to immediately find the proper index. This way you can find items without the need to search through the whole array.
If you like videos like this, it helps to tell Google+ with a click [googleplusone]
Code From the Video
Java Hash Table HashFunction.java
Hi Derek,
Great tutorial.
The implementation given above, is it linear probing (open addressing) collision avoidance strategy?
Thanks.
Thank you 🙂 Yes those are the technical words used to describe this type of hash table
a dumb question:
Why do u need to do the following line?
arrayIndex%=arraySize;
is it coz if u keep on incrementing the value might go above 30(arraysize)
If arrayIndex is equal to arraySize, this is a shortcut way to turn arrayIndex back to zero and then start back at the beginning of the array
Hi Derek, excellent tutorial.
in the findKey method, shouldn’t you be using equals method instead of == check ( int this line
if (theArray[arrayIndexHash] == key)
great job
Thank you very much 🙂
I am studying for a google interview and I came across your tutorial, really awesome!
Just a quick note, doesn’t the system go into infinite loop because at line 135:
135 arrayIndexHash %= arraySize;
you return to the start of the hash and you keep going until you “find” it. If I enter 411, the system go into finite loop mode.
Otherwise, really awesome tutorial and nicely commented code Derek, thanks!
Yes you are correct. I was supposing that the key would be in there and I shouldn’t have done that. Sorry about that. That is what happens sometimes when i write code out of my head.
Good luck on your interview 🙂
Hi, I am not sure, but don’t you have bug in findKey?
while (theArray[arrayIndexHash] != "-1") {..}– in case, that the value is presented in the array and the array is full, the loop will be infinite. Other case is that I miss something.
Anyway, great job with algorithms ;D,
thanks a lot.
correction:
in case, that the value is *NOT* presented
Because of this line Arrays.fill(theArray, “-1”) you’ll never have to worry about that problem. Sorry about any confusion
Hi Derek,
The tutorials are really great and i would expect from you that you come up with more and more tutorials like this on complete Java, J2EE, Frameworks like Spring Hibernate Ant Maven etc. Also if you could creat DVDs of all the topics (and many more), i mentioned above that would be really great and we can purchase them. As i would like to acquire indepth knowledge on Java and related stuffs.
Thanks
Channa
Hi Channa,
I will definitely cover all of the J2EE topics you mentioned. I just want to get the Android tutorial and C tutorial done first. Thank you for the requests. I’ll always provide my videos for free. I don’t plan on ever selling them.
Thank you, Derek!
I was wondering how to get out of the while loop, when the value is not found.
You’re very welcome 🙂 I’m glad I could help.
Hi Derek,
point to point explanation. excellent tutorials. expecting more Java J2ee framework tutorials from you. Thank you very much.
Thank you 🙂 I’ll cover jee as soon as possible
115 int arrayIndexHash = Integer.parseInt(key) % 29;
in the above statement can we choose any integer in the place of 29 which is less than 30? why have we chosen 29 instead of 30?
The 29 represents all the indexes. 0 through 29