HashMap的简单实现

Question

我实现了一个HashMap，它支持整数键值对的插入。这种方法为了简单起见使用了一个数组，并使用了一个标准的散列函数。请回顾一下程序中使用的编码方法。

import junit.framework.Assert;
import org.junit.Test;

public class HashMapImpl {
class HashMap {
    int SIZE_OF_TABLE = 128;
    HashEntry[] table;
    HashMap() {
        table = new HashEntry[SIZE_OF_TABLE];
        for (int i = 0; i < SIZE_OF_TABLE; i++) {
            table[i] = null;
        }
    }

    public void put(int key, int value) {
        int index = hashCodeNew(key);
        System.out.println(index);
        HashEntry hashEntry = new HashEntry(key, value);
        if (table[index] == null) {
            table[index] = hashEntry;
        } else {
            HashEntry runner = table[index];
            while (runner.next != null) {
                if (runner.key == hashEntry.key) {
                    runner.value = hashEntry.value;
                    break;
                } else {
                    runner = runner.next;
                }
            }
            if (runner.next == null) {
                if (runner.key == hashEntry.key) {
                    runner.value = hashEntry.value;
                } else {
                    runner.next = hashEntry;
                }
            }
        }

    }

    public int get(int key) {
        int index = hashCodeNew(key);
        if (table[index] == null) {
            return -1;
        } else {
            HashEntry runner = table[index];
            if (runner.key == key) {
                return runner.value;
            }
            while (runner.next != null) {
                if (runner.key == key) {
                    return runner.value;
                }
            }
            return -1;
        }
    }

    public int hashCodeNew(int h) {
        h ^= (h >>> 20) ^ (h >>> 12);
        int hashCode = h ^ (h >>> 7) ^ (h >>> 4);
        return hashCode % SIZE_OF_TABLE;
    }
}

class HashEntry {
    int key;
    int value;
    HashEntry next = null;

    HashEntry() {
    }

    public HashEntry(int key, int value) {
        this.key = key;
        this.value = value;
    }

    public int getKey() {
        return this.key;
    }

    public int getValue() {
        return this.value;
    }
}

@Test
public void testBasic() {
    HashMap hashMap = new HashMap();
    hashMap.put(10, 20);
    hashMap.put(20, 11);
    hashMap.put(21, 1);
    hashMap.put(20, 10);

    int value = hashMap.get(20);
    Assert.assertEquals(10, value);

}
}

Answer 1

HashEntry[] table目前在HashMap上公开，这是很危险的，因为任何人都可以搞砸它。应该是私密的。

HashEntry的字段也是如此。

在get中有些地方不对劲：

时间(runner.next != null) { if (runner.key == key) {返回runner.value；}}

runner.key永远不会等同于key。当执行到这里时，runner.next总是null。所以整个循环都没有用过，但我想你只是忘了一些东西。

该实现没有通过此单元测试：

@Test
public void test_1000_28() {
    HashMap hashMap = new HashMap();
    for (int i = 0; i < 28; ++i) {
        hashMap.put(i + 1000, i);
        assertEquals(i, hashMap.get(i + 1000));
    }
}

不要像这样混合JUnit 3和4：

进口junit.framework.Assert；进口org.junit.Test；

坚持其中一个(JUnit 4)：

进口org.junit.Assert；进口org.junit.Test；

所有大写字母仅用于常量。所以，不是这样的：

int SIZE_OF_TABLE = 128；

使用以下任何一种：

private static final int SIZE_OF_TABLE = 128;
//private final sizeOfTable = 128;
//private final tableSize = 128;

对象数组使用空值初始化。所以，不是这样的：

HashEntry[]表；HashMap() { table =新的HashEntry大小_的_表格；for (int i= 0；i< SIZE_OF_TABLE；i++) { table我 = null；}

您可以简化为：

HashEntry[] table;
HashMap() {
    table = new HashEntry[SIZE_OF_TABLE];
}

公共空置( int键，int值){int索引= hashCodeNew( key )；System.out.println(索引)；

不要打印到标准。我想您忘了在检查代码之前删除此调试行。

Answer 2

HashEntry[] table;
HashMap() {
    table = new HashEntry[SIZE_OF_TABLE];
    for (int i = 0; i < SIZE_OF_TABLE; i++) {
        table[i] = null;
    }
}

我会称它为正确的混淆。或者你的意思是

HashEntry[] table = new HashEntry[SIZE_OF_TABLE];

？它是Java，所有的东西都会被初始化(或者你得到一个编译时错误)。顺便说一句，一切都要保密。

public int hashCodeNew(int h) {
    h ^= (h >>> 20) ^ (h >>> 12);
    int hashCode = h ^ (h >>> 7) ^ (h >>> 4);
    return hashCode % SIZE_OF_TABLE;
}

这就打击了负值。最快的方法是确保table.length始终是2的幂，并使用

    return hashCode & (table.length-1);

我在这里使用的是table.length而不是SIZE_OF_TABLE，因为它应该能够成长。

Answer 3

我将使用一个素数来表示表的大小，因为输入中的任何间隔都将使用每个表槽(除非间距是表大小)。另外，散列函数不适用于负输入。在取余数之前，我会把输入乘以另一个大素数。

public int hashCodeNew(int h) {
    h = (h * (SIZE_OF_TABLE == 65537 ? 8191 : 65537)) % SIZE_OF_TABLE;
    if(h < 0)
        h += SIZE_OF_TABLE;
    return h;
}