• Post Reply Bookmark Topic Watch Topic
  • New Topic

Open / Closed Hashing  RSS feed

 
Callum Hughes
Greenhorn
Posts: 6
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi, I have a few questions in regards to Open & Closed Hashing when reviewing the internet there are few examples and clear definitions.

- What is Open and Close Hashing?
- What is the Difference between them both?
- Any Simple Java Related Examples Available?


Thanks any information or helpful resource corresponding to the above questions would be great
 
Campbell Ritchie
Marshal
Posts: 56534
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Never heard of either. You can try this Wikipedia article, which mentions open hashing, but it has a caveat about not using any references. See whether that helps. Or this sample chapter from the old edition of Effective Java™ by Joshua Bloch.
 
Gabriel John Gagno
Greenhorn
Posts: 5
IntelliJ IDE Java PHP
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
OPEN HASHING usually utilizes lists (besides the main array itself) to handle collisions as a result of the hashing function's output. Here's an example.

Suppose you have an array of data (assume zero-indexing)
data[0] = 1
data[1] = 2
data[2] = 3

to be hashed to an array hashtable called HashTable.

also suppose, by some hashing function, data[0] is assigned to HashTable[2]. The HashTable will now look like this:
[0]
[1]
[2] -> 1

now suppose that both data[1] and data[2] gets assigned to HashTable[1]. They will be placed then on the same index, only that they will be in a list, like this:

[0]
[1] -> 2, 3
[2] -> 1

CLOSED HASHING, on the other hand, differs in that it does not utilize lists to handle collisions; instead, it applies various mathematical methods to resolve the collision. Some use another hash function to reassign the number, while others resolve intervals either quadratically or linearly.

I am a computer science major in university and I learned this in my sophomore year.

Hope this helps!

Sources:
Aho, Hopcroft, Ullman: Data Structures and Algorithms: 1987: Addison-Wesley
 
Callum Hughes
Greenhorn
Posts: 6
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Gabriel John Gagno wrote:OPEN HASHING usually utilizes lists (besides the main array itself) to handle collisions as a result of the hashing function's output. Here's an example.

Suppose you have an array of data (assume zero-indexing)
data[0] = 1
data[1] = 2
data[2] = 3

to be hashed to an array hashtable called HashTable.

also suppose, by some hashing function, data[0] is assigned to HashTable[2]. The HashTable will now look like this:
[0]
[1]
[2] -> 1

now suppose that both data[1] and data[2] gets assigned to HashTable[1]. They will be placed then on the same index, only that they will be in a list, like this:

[0]
[1] -> 2, 3
[2] -> 1

CLOSED HASHING, on the other hand, differs in that it does not utilize lists to handle collisions; instead, it applies various mathematical methods to resolve the collision. Some use another hash function to reassign the number, while others resolve intervals either quadratically or linearly.

I am a computer science major in university and I learned this in my sophomore year.

Hope this helps!

Sources:
Aho, Hopcroft, Ullman: Data Structures and Algorithms: 1987: Addison-Wesley



Thanks for the Quick Reply, Do you have any additional Java Code Examples? :)
 
Carey Brown
Saloon Keeper
Posts: 3311
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Here's code for a simple hashmap implementation: click here
 
Junilu Lacar
Sheriff
Posts: 11477
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Gabriel John Gagno wrote:
I am a computer science major in university and I learned this in my sophomore year.

Sources:
Aho, Hopcroft, Ullman: Data Structures and Algorithms: 1987: Addison-Wesley

Welcome to the Ranch!

Ah, the venerable tome by Aho, Hopcroft, and Ullman. Some things never change. We had that as a reference way back when it was just published — tells you just how long I've been around. Trees, Stacks, Queues, Graphs, and all kinds of fun and interesting ADTs.

I'm an MSU-IITian myself but my sister got her MD from UP (IntarMed program). Welcome again, kabayan
 
Campbell Ritchie
Marshal
Posts: 56534
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Welcome again The method with the list is what java.util.HashMap uses, so that sounds like open hashing.
 
Gabriel John Gagno
Greenhorn
Posts: 5
IntelliJ IDE Java PHP
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Junilu Lacar wrote:
Gabriel John Gagno wrote:
I am a computer science major in university and I learned this in my sophomore year.

Sources:
Aho, Hopcroft, Ullman: Data Structures and Algorithms: 1987: Addison-Wesley

Welcome to the Ranch!

Ah, the venerable tome by Aho, Hopcroft, and Ullman. Some things never change. We had that as a reference way back when it was just published — tells you just how long I've been around. Trees, Stacks, Queues, Graphs, and all kinds of fun and interesting ADTs.

I'm an MSU-IITian myself but my sister got her MD from UP (IntarMed program). Welcome again, kabayan


Hello there kabayan. Thanks. I'm really just a senior student and I hope I can help in this place.
 
Gabriel John Gagno
Greenhorn
Posts: 5
IntelliJ IDE Java PHP
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
try this very simple implementation of a hash table. this one's for open hashing:

 
Stefan Evans
Bartender
Posts: 1837
10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Gabriel.

I think there are a couple of issues with your example here.
You have declared "dataList" as an ArrayList, but then reference it as an array?

Your hash function seems to depend on the size of the list... which is variable. So passing the same input to the hash function will potentially give a different answer - which goes against EVERYTHING I understand about a hash.
Given an input the same hash should ALWAYS be returned.

I think what you meant is for the dataList to be an array of Lists (so an open hash - each hash has a list of actual numbers against it)
And then the hash function dependant on the length of that array - which is fixed once it is created (assuming you don't recreate the array internally of course, in which case all bets are off)

So adding my interpretations on, here is the modified simple example.
Please feel free to point out that I'm just talking a load of bull here. This isn't my area of expertise.
 
Gabriel John Gagno
Greenhorn
Posts: 5
IntelliJ IDE Java PHP
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stefan Evans wrote:Hi Gabriel.

I think there are a couple of issues with your example here.
You have declared "dataList" as an ArrayList, but then reference it as an array?

Your hash function seems to depend on the size of the list... which is variable. So passing the same input to the hash function will potentially give a different answer - which goes against EVERYTHING I understand about a hash.
Given an input the same hash should ALWAYS be returned.

I think what you meant is for the dataList to be an array of Lists (so an open hash - each hash has a list of actual numbers against it)
And then the hash function dependant on the length of that array - which is fixed once it is created (assuming you don't recreate the array internally of course, in which case all bets are off)

So adding my interpretations on, here is the modified simple example.
Please feel free to point out that I'm just talking a load of bull here. This isn't my area of expertise.


Well yeah. this is actually a good implementation. I was in a hurry when I wrote my answers. thanks for pointing out some errors. Although actually, once you assign the length of the hashtable, it has to remain like that forever. Since your code says exactly what I mean, though, I believe you guys finally got my message. I can't think of any better examples for closed hashing, though. Just remember that in closed hashing, you don't use lists for each index; instead, you REASSIGN it using linear or quadratic probing, or using a different hash function (re-hashing).
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!