Hash Table Question

[Mj Lewis]

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?

public void E remove(K key) {
    int index = findIndex(key);
    E answer = null;

    if (index != -1) {
        answer = (E) data[index];
        keys[index] = null;
        data[index] = null;
        size--;
    }
    
    return answer;
}

[Dave Tolls]

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.

[Campbell Ritchie]

What is going to happen if that “bucket” has suffered a collision? You will now have this sort of situationdata[0] data[1] data[2] data[3]→→→node1→→→node2 data[4]→→→node0 data[5]→→→node3 data[6] data[7]→→→node4What 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]

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).

[Junilu Lacar]

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]

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]

The behavior is the same if you were dealing with int values:

int[] data = { ... };

data[i] = 10;

int answer = data[i];  // answer is now 10

data[i] = 0; // answer is still 10, not 0

[Junilu Lacar]

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]

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]

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:

List<E>[] data;

To Campbell's point though, you're probably better off with a Map<K, List<E>>.

[Mj Lewis]

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]

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]

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:

void foo () {
    int[] numbers = {1, 2, 3, 4};

    bar(numbers);

    System.out.println(Arrays.toString(numbers));
}

void bar(int[] nums) {
    nums[3] = 42;

    nums = new int[] {8, 10, 14, 75, 11};
}

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().