处理hash碰撞-开放地址法的简单实现

为什么使用开放地址法解决Hash冲突

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

1、链式地址法:从发生冲突的那个单元起,按照一定的次序,从哈希表中重新找到一个空闲的位置。
2、开放定址法: 链接地址法的思路是将哈希值相同的元素构成一个同义词的单链表。
3、再哈希法: 就是同时构造多个不同的哈希函数,当发生冲突时,用另一个函数进行计算,直到冲突不再产生。
4、建立公共溢出区:将哈希表分为公共表和溢出表,当溢出发生时,将所有溢出数据统一放到溢出区。

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

开放地址法实现

JDK的ThreadLocal使用了散列表存储多份线程变量,并用开放地址法解决Hash冲突,这里我们就参照
ThreadLocal里面的部分逻辑,用Java写一个精简的线性地址Hash表。

方案:使用线性探测实现,当出现Hash冲突后,从冲突位置开始,查找下一个空位置。
首先,我们创建LinearAddressMap类(由于数据在内存中是散列、线性存放的,所以暂且用LinearAddress命名),并定义私有属性和构造方法:

/**
 * linear address map
 *
 * @author anylots
 * @version $Id: LinearAddressMap.java, v 0.1 2020年10月31日 11:14 anylots Exp $
 */

public class LinearAddressMap<K, V> {

    /*** 初始容量 -- must be a power of two.*/
    private static final int INITIAL_CAPACITY = 16;

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

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

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

    /**
     * 初始化构造方法
     *
     * @param capacity
     */
    public LinearAddressMap(int capacity) {
        if (capacity == 0) {
            capacity = INITIAL_CAPACITY;
        }
        array = new Entry[capacity];
        setThreshold(capacity);
    }

Put operation

第一步,根据key和数组length计算出期望放入位置。
第二步,如果期望位置为空,直接放入;
第三步,如果不为空但key相同,则替换旧值;
第四步,期望位置已被其他数据使用,则从当前位置开始,循环查找下一个空位置(数组扩容阈值固定为2/3,所以始终会有空位置);
第五步,更新已使用空间计数,如果超过阈值,则进行数组扩容;

    /**
     * put operation
     *
     * @param key
     * @param value
     */
    public void put(K key, V value) {
        if (key == null) {
            throw new IllegalArgumentException("LinearAddressMap does not support null key");
        }
        Entry[] internalArray = array;
        int len = internalArray.length;
        int i = key.hashCode() & (len - 1);
        Entry e = internalArray[i];

        if (e == null) {
            //位置为空或key相等,替换旧值
            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; i < len; index = nextIndex(index, len)) {
            if (internalArray[index] == null) {
                internalArray[index] = new Entry((String) key, value);
                break;
            }
        }
        updateUsedSpace();
    }

Get operation

第一步,根据key和数组length计算出期望位置。
第二步,期望位置Miss,则从当前位置开始,循环查找匹配的key;

    /**
     * get operation
     *
     * @param key
     * @return
     */
    public Object get(String key) {
        if (key == null) {
            throw new IllegalArgumentException("LinearAddressMap does not support null key");
        }
        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);
        }
    }

    /**
     * get entry after miss
     *
     * @param key
     * @param i
     * @param e
     * @return
     */
    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;
    }

数组扩容

新定义一个两倍大小的新数组,再将原数组元素重新Hash(根据新数组length),放入新数组:

    /**
     * array resize,Double the capacity of the table
     */
    private void arrayResize() {
        Entry[] oldArray = array;
        int oldLen = oldArray.length;
        int newLen = oldLen * 2;
        //定义新的数组
        Entry[] newArray = new Entry[newLen];
        int count = 0;
        //遍历旧数组
        for (int j = 0; j < oldLen; ++j) {
            Entry e = oldArray[j];
            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;
    }

性能测试

进行简单的性能测试,100条数据,分别读取、写入测试,记录总运行时间及内存占用:

    public static void main(String[] args) {

        List<String> keyList = new ArrayList<>(1000);
        for (int i = 0; i < 1000; i++) {
            keyList.add(UUID.randomUUID().toString());
        }

        long startTime = System.currentTimeMillis();
        for (int i = 0; i < 100000; i++) {
            linearAddressMapTest(keyList);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("LinearAddressMap program time consuming:" + (endTime - startTime) + "ms");
    }

    private static void linearAddressMapTest(List<String> keyList) {
        LinearAddressMap<String, Object> linearAddressMap = new LinearAddressMap(16);
        for (String key : keyList) {
            linearAddressMap.put(key, key);
        }

        for (String key : keyList) {
            Object testValue = linearAddressMap.get(key);
        }
    }
测试结果:

1、总耗时:线性寻址LinearAddressMap使用时间为2971ms,同样条件下HashMap用时3452ms;
2、堆空间使用:Old Generation差别不大,LinearAddressMap的Young Generation占用稍大于HashMap;

LinearAddressMap Heap Usage:

Eden Space:
   capacity = 413138944 (394.0MB)
   used     = 132134880 (126.01364135742188MB)
   free     = 281004064 (267.9863586425781MB)
   31.98315770492941% used

HashMap Heap Usage:

Eden Space:
   capacity = 413138944 (394.0MB)
   used     = 115653008 (110.29530334472656MB)
   free     = 297485936 (283.70469665527344MB)
   27.993731813382375% used
原因分析:

照理来说,在线性寻址法中,数据都put在一个一维数组中,和链表法相比,冲突的概率更高。
但是可以将线性寻址法的数组扩容阈值设置的小一点(HashMap虽然也可以同样操作,但数据仍然不能完全线性分布),来保持较大的容量,从而提高平均查找速度。
HashMap的链表法指针需要额外的空间,且相比一维数组需要更多的cpu计算资源,而若将节省的指针空间用来扩大散列表的规模,可使装填因子变小,这又减少了开放寻址法中的冲突。

未分类>
匿名

发表评论

匿名网友