首页 > 代码库 > 聊聊Hash

聊聊Hash

2024-07-28 02:53:46   223人阅读

最近近在看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;
        }

        @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的文章来说明一下.

聊聊Hash


联系
我们