• 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
  • Junilu Lacar
  • Martin Vashko
Sheriffs:
  • Jeanne Boyarsky
  • Tim Cooke
  • Knute Snortum
Saloon Keepers:
  • Ron McLeod
  • Tim Moores
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
Bartenders:
  • Scott Selikoff
  • salvin francis
  • Piet Souris

Hash Table Question

 
Greenhorn
Posts: 8
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi everyone,

I am working through an implementation of the hash table collection and have a question regarding a few methods. For example, I included an implementation of the remove method below. My question is about the following three operations:

1) answer = (E) data[index];
2) data[index] = null;
3) return answer;

QUESTION: The element in data[index] is an object that answer now refers to. However, we the change that object to be a null reference. So, why doesn't answer now reference the null object? Shouldn't this follow the whole "pass by value / pass by reference" logic whereby any changes to the underlying object should impact everything that references it?

 
Master Rancher
Posts: 4371
47
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
When you set a reference variable to null, you are not doing anything to the original object, you are simply changing the reference to point to null.

It's like a piece of paper (reference variable) with an address (location on the heap) on it.
If I rub out the address on the paper then I am not actually deleting the house the address referred to, I am simply removing it from the piece of paper.
 
Marshal
Posts: 66637
251
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
What is going to happen if that “bucket” has suffered a collision? You will now have this sort of situationWhat if you remove the pair represented by node1? If you simply null out the element in the backing array, you will lose the connection to node2.

What do you mean by, “the null object”? Remember there is no such thing. You are only changing the state of the array, as DT has implied, and that object should only be visible inside the map implementation.
 
Campbell Ritchie
Marshal
Posts: 66637
251
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Good grief! Have you got separate keys and data arrays? I don't like parallel arrays; I think it is a very error‑prone approach. Create pair objects (or better still, Map.Entry<K, V> objects).
 
Marshal
Posts: 14530
242
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:Good grief! Have you got separate keys and data arrays? I don't like parallel arrays; I think it is a very error‑prone approach. Create pair objects (or better still, Map.Entry<K, V> objects).



He's trying to implement a HashTable and those are internal data structures that are managed by the object itself, i.e. it's encapsulated. Maintaining them as parallel structures in this case is not really that gross. Map entries may push down some logic but for learning purposes, I think this is fine.
 
Junilu Lacar
Marshal
Posts: 14530
242
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Mj Lewis wrote:
QUESTION: The element in data[index] is an object that answer now refers to. However, we the change that object to be a null reference. So, why doesn't answer now reference the null object? Shouldn't this follow the whole "pass by value / pass by reference" logic whereby any changes to the underlying object should impact everything that references it?


What you seem to think should happen:

1. data[index] --> (E)

2. answer --> data[index] --> (E)

3. answer --> data[index] --> null

What is actually happening:

1. data[index] --> (E)

2. data[index] --> (E) <-- answer

3. data[index] --> null
                   (E) <-- answer
 
Junilu Lacar
Marshal
Posts: 14530
242
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The behavior is the same if you were dealing with int values:
 
Junilu Lacar
Marshal
Posts: 14530
242
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Mj Lewis wrote:Shouldn't this follow the whole "pass by value / pass by reference" logic whereby any changes to the underlying object should impact everything that references it?


The behavior has nothing to do with pass by value or by reference. By the way, in Java everything is passed by value. It's incorrect to think that anything is passed by reference. Even reference variables are passed by value. It's critical that you understand that concept otherwise you'll confuse yourself, just as in this case.
 
Campbell Ritchie
Marshal
Posts: 66637
251
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
As Junilu points out, you can get away with parallel arrays when things are nice and simple, but have another look at my diagram with the collision. If you want to remove node1, you are going to have problems retaining node2, which was added at the same location in the array because the right ends of the hash codes were the same. It is bad enough if you are in one array, but I can see those problems being worse if you are working with two distinct objects in two different arrays. Remember that both the K and the V will need links to their successors whether you have one array or two.
The numbers 1000008 and 56 have the same rightmost four bits, each 1000. If those two hash codes happen to come up in a small collection with a 16‑element backing array, you have a collision. Collisions are nothing to worry about in a small collection, but you need to be careful about those two values that in removing one you don't remove the other.
 
Junilu Lacar
Marshal
Posts: 14530
242
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Here's a property of hash codes that relate to Campbell's point about collisions: hash codes are required to be the same for two objects that are considered equal with the equals() method. However, if two objects are NOT equal according to the equals() method, it is NOT necessary that their hash codes are also not equal. In other words, if two objects are equals(), then their hash codes MUST be equal. If they are not equals(), their hash codes MAY or MAY NOT be equal.

If you're going to maintain parallel arrays, each element of the data array should at least be able to hold references to multiple objects whose hash codes are equal but are not necessary equals() themselves. That would imply something like this instead:

To Campbell's point though, you're probably better off with a Map<K, List<E>>.
 
Mj Lewis
Greenhorn
Posts: 8
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Junilu Lacar wrote:

Mj Lewis wrote:Shouldn't this follow the whole "pass by value / pass by reference" logic whereby any changes to the underlying object should impact everything that references it?


The behavior has nothing to do with pass by value or by reference. By the way, in Java everything is passed by value. It's incorrect to think that anything is passed by reference. Even reference variables are passed by value. It's critical that you understand that concept otherwise you'll confuse yourself, just as in this case.



I thought I understood this, but let me test my thought process...do you mind confirming?

I agree that everything in Java is pass by value; however, when you're dealing with objects, the value that is passed is a memory address. So if a local variable then is initialized to the argument, then the local variable references that same object that was passed as an argument. Therefore, any changes within a method are visible to the outside world because what we really changed was something at a memory address that multiple reference variables (regardless of scope) might refer to.
 
Mj Lewis
Greenhorn
Posts: 8
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Junilu Lacar wrote:

Mj Lewis wrote:
QUESTION: The element in data[index] is an object that answer now refers to. However, we the change that object to be a null reference. So, why doesn't answer now reference the null object? Shouldn't this follow the whole "pass by value / pass by reference" logic whereby any changes to the underlying object should impact everything that references it?


What you seem to think should happen:

1. data[index] --> (E)

2. answer --> data[index] --> (E)

3. answer --> data[index] --> null

What is actually happening:

1. data[index] --> (E)

2. data[index] --> (E) <-- answer

3. data[index] --> null
                   (E) <-- answer



The most helpful diagram ever! Thank you!
 
Junilu Lacar
Marshal
Posts: 14530
242
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
So far so good. Make sure you also understand that changes to the reference itself (not the referenced object) do not propagate outside of the method.

To illustrate that with an example:

Calling foo() will print [1, 2, 3, 42], not [8, 10, 14, 75, 11}

Line 10, the change to nums[3] propagates outside to affect numbers[3] in foo() because nums and numbers reference the same array object. However, line 12 changes nums to reference a different array object but that doesn't change what numbers references in foo().
 
I am going down to the lab. Do NOT let anyone in. Not even this tiny ad:
Java file APIs (DOC, XLS, PDF, and many more)
https://products.aspose.com/total/java
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!