Win a copy of Head First Go this week in the Go forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Bear Bibeault
  • Paul Clapham
  • Jeanne Boyarsky
Sheriffs:
  • Devaka Cooray
  • Junilu Lacar
  • Tim Cooke
Saloon Keepers:
  • Tim Moores
  • Ron McLeod
  • Tim Holloway
  • Claude Moore
  • Stephan van Hulst
Bartenders:
  • Winston Gutkowski
  • Carey Brown
  • Frits Walraven

Question to using "separate chaining with linked lists" technique for collision  RSS feed

 
Ranch Hand
Posts: 53
3
IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
So I have been dabbling with Hashtables and LinkedLists these days.
I wrote a Hashtable class that should safe Strings based on their ASCII values
First a little summary of what I have learned so far. It helps me articulating my question and it hopefully helps you understanding my problems.
So far what I have understood is:
A hashtable is basically a class that includes an Array. When I want to store data in a object of the type Hashtable i use the hash() method to find a hashcode. In my own Hastable class i simply used the ASCII values of all the letters and symbols of the Strings that I wanted to safe in my Hashtable.  
A LinkedList is a List where the LinkedList itself stores a reference to the newest object, to the object which has been added last. This object contains a reference to the object added before this one and so on and so forth. The reference is simply a variable of the right type that indicates on the object in question. One of the major differences as far as I understood it is that ind a LinkedList you can not simply find the value for the key xy, instead you have to start either at the beginning of the list or at the end and iterate through the list to find what you are looking for.
So if I have the Strings xam and max they will collide. One solution (and the one I want to use) is "separate chaining with linked lists". But will the LinkedList that I write be a second list in addition to the hashtable Array that is already in use? Or do I have to delete the initial code?
If the former is the case, will I simply include an if condition ? Something like


Thanks in advance!
Louis
 
Saloon Keeper
Posts: 9869
199
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Really, most hash table implementations are based on an array of lists, each list called a bucket. An element gets added to a bucket in a location based on the hash.

Having a separate list from the array doesn't have much sense.

I also advise against linked lists, they are not going to be as performant as an array list.
 
Louis Müller
Ranch Hand
Posts: 53
3
IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Alright thanks, that was really helpful. I think I have to use a LinkedList to get full points in the assignment Im doing right now. Since Im a fullblood greenhorn, it probably wont do no harm to practice this technique even tho it is considered bad practice.
So this means that, to change my not-collision-proof hashtable to a collision proof one, i simply add the methods and references needed to mak the list that I am using right now (a simple array) a LinkedList. Therefore a LinkedList is just an array with certain specifications of the objects?!
 
Stephan van Hulst
Saloon Keeper
Posts: 9869
199
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
No, the outer structure must be an array, otherwise you won't be able to perform hash lookups in constant time, defeating the purpose of having a hash table in the first place.

What I meant was, each element of the array (each bucket) can be an ArrayList, rather than a LinkedList. However, if you must implement this structure yourself, rather than using the predefined types in the collections API, then a linked list is easier to implement yourself.

Imagine that you write a custom list type (regardless of whether it's based on linked nodes or an array) and call it Bucket. The main data structure of your custom hash table would then be a Bucket[] ("array of buckets").

When you want to store a value, it pretty much goes like this: Get an initial hash code from the object you want to store. You could just call hashCode(), but if your assignment calls for you to work with strings only and to create your own hash code based on their ASCII encoded value, then do that. Then you have to apply some function that gets a bucket index from the hash code. The % operator is a very simple way to do this. Then you just add the element to the Bucket at that index.

Note that the amount of collisions you get will increase drastically as the table gets fuller. So it's a good idea to keep track of how many elements you've already added and divide it by the size of the bucket array. If this ratio gets too large, you need to rehash the entire table with a larger array of buckets to prevent more hash collisions.
 
Marshal
Posts: 63496
207
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You will have to traverse each bucket regardlesss, so that part of the search will run in linear time. That is why hash collections usually have a load factor (for HashMap it defaults to 75%, I believe), so a good hashCode() implementation will spread the entries evenly across the array and most buckets will have a size of 1; at least 25% of the buckets will have a size of 0. So you are going to worry what sort of List you are traversing in the buckets.

I believe that Java9+ versions of HashMap implement their buckets slightly differently, but I might be mistaken.
 
Marshal
Posts: 6595
443
BSD Linux Mac OS X VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:I believe that Java9+ versions of HashMap implement their buckets slightly differently, but I might be mistaken.


To my knowledge, since Java 8, when the collisions reach certain threshold, instead of Lists, Red-Black trees are being used.
 
Louis Müller
Ranch Hand
Posts: 53
3
IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Alright, so a LinkedList is a 2D array is that correct? Because its an array of buckets and buckets in itself are sort of a list as well.
 
Louis Müller
Ranch Hand
Posts: 53
3
IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Oh no I just realised I got that entirely wrong. I rethink this and come back.
 
Campbell Ritchie
Marshal
Posts: 63496
207
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Louis Müller wrote:Alright, so a LinkedList is a 2D array is that correct? . . . .

A linked list usually comprises nodes, one for each element; each node is linked to one of its neighbours. A doubly‑linked list has its nodes linked to both their neighbours. Linked lists don't usually contain arrays unless that is their element type.
 
Louis Müller
Ranch Hand
Posts: 53
3
IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ok but if I want to store Strings in a Hashtable I am to use an array of Link-objects to use the technique of separate chaining with a LinkedList. It seems inpractical to me to use a String array as long as there is only one String with the same hashcode and then suddenly switch to a LinkedList if a collision appears.
Because that is what my assignment sounded like. I tried this now and it seems rather complicated.
 
Louis Müller
Ranch Hand
Posts: 53
3
IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Just noticed that I made a mistake! I have to use an array of LinkedLists !!!
So the array store has to be of the type LinkedList is that correct?
 
Sheriff
Posts: 5750
149
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That sounds correct, if your HashTable is an array and the hash is an index into that array.
 
Louis Müller
Ranch Hand
Posts: 53
3
IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That is the case, thank you Knut.

The next issue Im having here is with the add(String data) method of my LinkedList class.
I wrote it like this:



This will create a new Link object by calling the constructor with 2 arguments, data and root.
My constructor looks like this:



Isn't this bound to give me a NullPointerException when I add an element for the first time to this index?
In that case, root will be null and nextLink will point to null.
I actually got an NullPointerException and this is the reason I came up with is that correct?
 
Louis Müller
Ranch Hand
Posts: 53
3
IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
My solution for this would be to write 2 add methods.
addFirst(String data)
and
add(String data)

I would change only the constructor that gets called when creating the new Link object.
 
Knute Snortum
Sheriff
Posts: 5750
149
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I would think adding logic to the add() method to know when it is adding for the first time would be better.
 
Stephan van Hulst
Saloon Keeper
Posts: 9869
199
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It's not going to be practical to skip making list nodes, because even if you only have one value associated with a bucket, you still need to encapsulate it in an object that contains both the key AND the value, and then you might as well add a member that links to the next node. It would look something like this:

 
 
Louis Müller
Ranch Hand
Posts: 53
3
IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
As far as I can judge this, you are absolutely right in general. But I think for my assignement the key is the index of my array. I calculate the sum of the ASCII values of all the letters and symbols (excluding spaces) in the string and return the value of sum % 31 (The Array length which is fixed)
This is an extremely simplified version of an actual HashTable i guess. I therefore dont have to store Key and value in my object. Please correct me if Im wrong!
 
Stephan van Hulst
Saloon Keeper
Posts: 9869
199
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Let's say you have two colliding keys, "abc" and "cba". How are you going to prevent returning the value for "abc" when you want to get the value for "cba"?
 
Louis Müller
Ranch Hand
Posts: 53
3
IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I was planning to use String.equals to figure out which of the two is the right one. Would it be a solution to put it in an object containing key and value? The key would still be the same and I'd have to check whether or not the objects are equal.
 
Louis Müller
Ranch Hand
Posts: 53
3
IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I still get that NullPointerException.
I get it when trying to find a String that hasnt been added yet. For example the String Hello. If the first command is find "Hello" I get the NullPointerException.

The relevant code:

the find method of my (self written) Hashtable class:


The find() method of my Linked List class





The rest of my code, hopefully the above code will be sufficient so you dont have to work your way through all of this:
 
Louis Müller
Ranch Hand
Posts: 53
3
IntelliJ IDE Java
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Since My original question has been answerered, I will start a new Thread for my last question
 
The only cure for that is hours of television radiation. And this tiny ad:
Become a Java guru with IntelliJ IDEA
https://www.jetbrains.com/idea/
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!