面试经典-基于开放地址手写hashmap

一、解决Hash冲突的四种方式

由于哈希值的空间远小于输入的空间，所以经过散列处理后，仍然会出现不同的数据对应相同的数组下标，这时候就产生了哈希冲突。为了解决哈希冲突，有以下四种方法：

1. 链式地址法：从发生冲突的那个单元起，按照一定的次序，从哈希表中重新找到一个空闲的位置。
2. 开放地址法： 当发生地址冲突时，按照某种方法继续探测哈希表中的其他存储单元，直到找到空位置为止。
3. 再哈希法： 就是同时构造多个不同的哈希函数，当发生冲突时，用另一个函数进行计算，直到冲突不再产生。
4. 建立公共溢出区：将哈希表分为公共表和溢出表，当溢出发生时，将所有溢出数据统一放到溢出区。

二、源码中的应用

Java中的HashMap采用的是链式地址法，是一种寻址相对容易，插入也较容易的数据结构。
但是当数量不大，可用空间大，性能要求高，或者就要求数据线性排列，那么采用开放定址法会有优异的效果，实际上Python中的Dictionary、Java中ThreadLocal，就是使用开放寻址法解决冲突的。

三、代码

public class CustomMap {
    // 初始容量
    private static final int INITIAL_CAPACITY = 16;

    // 一维数组
    private Entry[] array;

    // 数组扩容阈值
    private int threshold;

    // 已使用空间
    private int usedSize = 0;

    class Entry {
        String key;
        Object value;

        Entry(String key, Object value) {
            this.key = key;
            this.value = value;
        }

        public String getKey() {
            return key;
        }

        public Object getValue() {
            return value;
        }
    }

    public LinearAddressMap(int capacity) {
        if (capacity == 0) {
            capacity = INITIAL_CAPACITY;
        }
        array = new Entry[capacity];
        setThreshold(capacity);
    }

    public void put(K key, V value) {
        if (key == null) {
            throw new IllegalArgumentException("key is null");
        }
        Entry[] internalArray = array;
        int len = internalArray.length;
        int i = key.hashCode() & (len - 1);
        Entry e = internalArray[i];

        if (e == null) {// 位置为空
            internalArray[i] = new Entry((String) key, value);
            updateUsedSpace();
            return;
        }

        if (e.getKey().equals(key)) {// key相等，替换旧值
            internalArray[i] = new Entry((String) key, value);
            return;
        }

        //出现hash冲突，从冲突位置开始，查找下一个空位置
        for (int index = i; index < len; index = nextIndex(index, len)) {
            if (internalArray[index] == null) {
                internalArray[index] = new Entry((String) key, value);
                break;
            }
        }
        updateUsedSpace();
    }

    private int nextIndex(int index, int len) {
        index++;
        return index % len;
    }

    public Object get(String key) {
        if (key == null) {
            throw new IllegalArgumentException("key is null");
        }
        int i = key.hashCode() & (array.length - 1);
        Entry e = array[i];
        if (e != null && e.getKey().equals(key)) {
            return e.getValue();
        } else {
            return getEntryAfterMiss(key, i, e);
        }
    }

    private Object getEntryAfterMiss(String key,int i,Entry e){
        Entry[] tab = array;
        int len = tab.length;
        while (e!= null){
            String k = e.getKey();
            if (k.equals(key)){
                return e.getValue();
            }else {
                i = nextIndex(i,len);
            }
            e = tab[i];
        }
        return null;
    }

    private void arrayResize(){
        Entry[] oldArray = array;
        int oldLen = oldArray.length;
        int newLen = oldLen * 2;
        Entry[] newArray = new Entry[newLen];
        int count = 0;
        for (int i = 0; i < oldLen; i++) {
            Entry e = oldArray[i];
            if (e != null){
                String k = e.getKey();
                int h = k.hashCode() & (newLen -1);
                while(newArray[h] != null){
                    h = nextIndex(h,newLen);
                }
                newArray[h] = e;
                count++;
            }
        }

        setThreshold(newLen);
        usedSize = count;
        array = newArray;
    }
}