聊一聊hash

最近近在看java里面ThreadLocal里面对于ThreadMap的查找使用的是Hash算法,还提到了神奇数字,于是深入的看了hash这个东西,下面就来掰扯一下hash的原理,搞懂原理了,其实对于hashmap或者hashset这种类也就很好理解,无非就是算法选择的不同而已.

首先一个问题:hash是什么?
其实hash应该叫哈希函数,就是从给定的一个key开始,根据一定的算法来计算出一个唯一值即:f(Key)=hashCode,要求是通过f的函数计算后key和这个hash值是保持一对一的唯一关系.很多地方说适用于寻址,这也是用法之一,像MD5这种摘要算法就是仅仅用于校验的.

用程序来说明一下hash是做什么用的:
先定义一个接口,就两个方法,一个是生成hash值一个是通过hash值获取对象.

public interface HashInterface {
	/* 生成hash */
	public int hash(Object value);
	/* 通过hash获取对象,可以看成是寻址的过程 */
	public Object get(int hash);
}

现在实现一个采用直接寻址法的hash方法:

public class Hash implements HashInterface {

    private final Object[]  tables;

    public Hash1(int tablesSize) {
        tables = new Object[tablesSize];
    }
    /*此处是其实下标,如果数组要的前几位需要被预留,则seed射为预留的个数*/
    private int hashSeed    = 0;

    @Override
    public int hash(Object value) {
        if (hashSeed == tables.length - 1) {
            throw new IndexOutOfBoundsException("已经超出hash范围");
        }
        int hash = hashSeed++;
        tables[hash] = value;
        return hash;
    }

    /*
     * (non-Javadoc)
     * @see com.coffee.tesch.test.HashTest.HashInterface#get(int)
     */
    @Override
    public Object get(int hash) {
        return tables[hash];
    }
}

是不是看了代码以后觉得这就是数组里面按照顺序放进去,然后返回的hash值就是数组下标嘛.基本上最简单的hash就是这样的,它的数学原型就是f(x)=a*x+b,简单吧.举这个例子,只是想说明一下hash主要是保证在规定的范围内Key对应hash值不重复,这里要注意的一个是”限定的存储(哈希表)范围”,还有就是”不重复”.原理就是这样的,基本上你的算法实现在hash(Object value)里面随意变换算法,只要保证在限定范围内计算出的hash是唯一的就可以了.具体可以google一下hash,有很多种实现算法.
但是要保证计算出来的hash值不重复貌似真的很难,数学家也没法保证f(x)!=f(x1),我们把这种不一样的key但是最后算出来一样的hash值的现象叫做碰撞,为了解决碰撞又有很多种方式,什么开地址发,什么线性探测再散列,反正我不是研究数学的,只要知道是怎么做的就行了,看下面的例子:

public class Hash2 implements HashInterface {

    private final Object[]  tables;

    private int             mod;
    /**
     * 再探测地址增量
     */
    private int             d;

    private int             hashSeed    = 0;

    public Hash2(int tablesSize) {
        tables = new Object[tablesSize];
        mod = tablesSize;
    }

    @Override
    public int hash(Object value) {
        int index = (value.hashCode() + d) % mod;
        if (tables[index] != null) {
            if (d == mod) {
                throw new IndexOutOfBoundsException("已经超出hash范围");
            }
            d++;
            return hash(value);
        }
        return index;
    }

    @Override
    public Object get(int hash) {
        return tables[hash];
    }

}

这个例子里面计算hash的方式是采用取余的方式计算hash,但是不能保证每次取余的结果都不一样,比如32和52对10取余都是2,这个时候怎么办,我们增加一个增量地址,如果发现2这个hash位置上已经有值了我就把d++,看看3上面有没有值,没有的话就直接填入,并返回3为hash值.其他的避免碰撞的方法很多,如果要深入的研究的话请自己去查资料.

基本上讲到这里最简单的hash都将完了,大家对hash应该有一个初步的概念了,而不是单纯的理论,在java的ThreadLocal里面有一个神奇的hash数字0x61c88647,这个有点类似黄金分割的味道,可以保证hash值是均匀散列的,看下面的代码:

static int  HASH_INCREMENT  = 0x61c88647;
static int  hash            = 0;

private static int nextHash() {
    int i = hash;
    hash = i + HASH_INCREMENT;
    return i;
}

public static void main(String[] args) {
    for (int j = 0; j < 4; j++) {
        int size = 2 << j;
        // hash = 0;
        int[] indexArray = new int[size];
        for (int i = 0; i < size; i++) {
            indexArray[i] = nextHash() & (size - 1);
        }
        System.out.println(Arrays.toString(indexArray));
    }

}

结果是:

[0, 1]
[2, 1, 0, 3]
[2, 1, 0, 7, 6, 5, 4, 3]
[2, 9, 0, 7, 14, 5, 12, 3, 10, 1, 8, 15, 6, 13, 4, 11]

我没有看到重复的索引值(你完全可以把这个看作是hash值),只要哈希表的大小是2的N次方,那么基本上可以保证每次计算出的hash值都不会重复,但是我不保证例外,哈哈
其实上面的代码里面还有一个bug,就是在hash表动态扩展大小的时候,很大的可能导致hash碰撞,所以再每次计算出hash值以后需要再判断一下hash对应下标的位置有没有值,如果有值的话需要再此计算hash.
总的说来,hash的效率还是比较高的,总比线性的一个一个判断是否有值要高效很多,就算发生碰撞了,再计算一次也很容易找到位置为空的地方存放数据.
基本上关于hash的东西就这么些,还有hashMap,hashSet这些也都是用到到hash的原理来处理数据的索引,下次再看到的时候我再补充一篇专门针对hashMap和HashSet的文章来说明一下.