关于哈希Hash

Hash，一般翻译做散列、杂凑，或音译为哈希，是把任意长度的输入（又叫做预映射pre-image）通过散列算法变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来确定唯一的输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。 白话：给你一(多)个字符串(数据)，你根据字符串生产一个唯一的hash数

常用Hash函数

直接寻址法

取关键字或关键字的某个线性函数值为散列地址，即H(key)=key或H(key) = a·key + b，其中a和b为常数

数字分析法

分析一组数据，比如一组员工的出生年月日，这时我们发现出生年月日的前几位数字大体相同，这样的话，出现冲突的几率就会很大，但是我们发现年月日的后几位表示月份和具体日期的数字差别很大，如果用后面的数字来构成散列地址，则冲突的几率会明显降低。因此数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。

平方取中法

取关键字平方后的中间几位作为散列地址。

折叠法

将关键字分割成位数相同的几部分，最后一部分位数可以不同，然后取这几部分的叠加和（去除进位）作为散列地址。

随机数法

选择一随机函数，取关键字作为随机函数的种子生成随机值作为散列地址，通常用于关键字长度不同的场合。

除留余数法

取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p,p<=m。不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。对p的选择很重要，一般取素数或m，若p选的不好，容易产生碰撞。

处理Hash冲突方案

哈希冲突即是，不同的数据，经过同一个hash函数，生成了同一个hash值。

开放寻址法

Hi=(H(key) + di) MOD m，i=1,2,…，k(k<=m-1)，其中H(key)为散列函数，m为散列表长，di为增量序列，可有下列三种取法：

1. di=1,2,3,…，m-1，称线性探测再散列；
2. di=1^2,-1^2,2^2,-2^2,3^2,…，±k^2,(k<=m/2)称二次探测再散列；
3. di=伪随机数序列，称伪随机探测再散列。

说的通俗一点，如果这个Hash冲突了，则根据上诉计算方式，尝试寻找下一个没有被占用地址的位置，就比如hash计算出来得1，则array[1]里面已经本占用了，这个时候可以根据方法1，计算得到下一个地址为2，如果2地址也被占用了，则3以此类推。直到找到没有被占用得即可。

再散列法（再哈希）

Hi=RHi(key),i=1,2,…，k RHi均是不同的散列函数，即在同义词产生地址冲突时计算另一个散列函数地址，直到冲突不再发生，这种方法不易产生“聚集”，但增加了计算时间。

链地址法(拉链法)

拉链法就是用一个数组存hash过后的地址值，地址值后面存这个hash值得链表，当hash冲突之后，则只需要将冲突的数据连接到这个链表之后就行了，这样有个问题就是增加了空间成本，而且还有个问题就是查找可能出现问题。当某个hash值冲突严重的时候，这个链表可能会非常的长，如果查找一个数据就需要根据hash找到链表，然后遍历链表找到真正的数据。所以可能性能上有些影响，在Java(1.8)的HashMap里面，是在链表长度到达一定长度之后，链表转化成了红黑树。

建立公共溢出区

建立一个公共溢出区域，就是把冲突的都放在另一个地方，不在表里面。

平均查找长度与装填因子

1. 平均查找长度 为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度()，ASL成功。 在查找表中查找不到待查元素，但是找到待查元素应该在表中存在的位置的平均查找次数称为查找不成功时的平均查找长度，不成功。
2. 装填因子 散列表的装填因子定义为：α= 填入表中的元素个数/散列表的长度 装填因子越大，说明hash表装的越多，冲突出现越大。

影响Hash表性能的因素

1. 因素
   • 散列函数是否均匀；
   • 处理冲突的方法；
   • 散列表的装填因子。
2. 著名Hash算法
   • MD4
   • MD5
   • SHA-1

用Java实现Hash表

使用了开放地址法和拉链法。

/**
 * Hash表的Java实现
 * @author unclezs.com
 * @date 2019.06.04 18:51
 */
public class MyHashTable<K, V> {
    private int num = 0;//索引使用数量
    private int capacity;//容量
    private Node<K, V>[] table;//散列表
    private int mode = 1;//处理冲突方式 1开放地址法，2链表储存法
    private double eRate = 0.8;//扩容因子（达到容量的多少比例后扩容）
    private int hashMode;//哈希值生成函数选择
    private int conflictsNum;//冲突次数
    private int linkNodeNum;//链式储存时当前节点个数
    private int queryNum;//查询一次比较次数

    //默认容量16
    public MyHashTable() {
        this(16);
    }

    //构建散列表
    public MyHashTable(int capacity) {
        this.capacity = capacity;
        table = new Node[capacity];
    }

    /**
     * 高级构造
     *
     * @param capacity 容量
     * @param mode     处理冲突方式
     * @param eRate    扩容因子
     */
    public MyHashTable(int capacity, int mode, double eRate, int hashMode) {
        this(capacity);
        this.mode = mode;
        this.eRate = eRate;
        this.hashMode = hashMode;
    }

    //散列函数
    public int hash(K key) {
        if (hashMode == 1) {//余数法
            return (key.hashCode() & 0x7fffffff);
        } else {//折叠法+余数法
            int code = key.hashCode() & 0x7fffffff;
            //1865644118
            int h = code / 1000000;//186
            h += code / 1000 % 1000;//564
            h += code % 1000;//118
            return h;
        }
    }

    //添加数据（三种情况，还没有初始化hash表，初始化了但是hash值冲突，key相同）
    public void put(K k, V v) {
        //自动扩容，2倍扩容
        if (num > eRate * capacity && mode == 1) {
            resize(capacity * 2);
        }
        int hash = hash(k);//计算哈希值
        int index = indexFor(hash);//计算索引
        //如果没有冲突
        if (table[index] == null) {
            table[index] = new Node<>(k, v, hash);
            linkNodeNum++;
            conflictsNum++;
        } else if (mode == 1) {//开放地址法解决冲突
            if (hash == table[index].hash && (k.equals(table[index].getKey()))) {//如果键的值一样且与上次hash值相同则更新
                table[index].setValue(v);
                conflictsNum++;
                return;
            } else {//确认为冲突
                while (table[index] != null) {
                    conflictsNum++;
                    //找到可以插入的索引
                    index = (index + 1) % capacity;
                }
                table[index] = new Node<>(k, v, hash);
            }
        } else if (mode == 2) {//链式储存法解决冲突
            //判断是否为过更新
            Node<K, V> node = table[index];
            while (node.next != null && !node.getKey().equals(k)) {//遍历找到末尾节点或者找到键值相同的节点
                node = node.next;
                conflictsNum++;
            }
            if (node.getKey().equals(k)) {
                node.setValue(v);
                return;
            }
            //非更新
            linkNodeNum++;
            conflictsNum++;
            node.next = new Node<K, V>(k, v, hash);
            return;
        }
        num++;//当前表中索引使用数量增加
    }

    //删除数据
    public void remove(K k) {

    }

    /**
     * 查询数据
     *
     * @param k key值
     * @return 没找到返回null
     */
    public V get(K k) {
        queryNum = 1;
        int hash = hash(k);
        int index = indexFor(hash);
        Node<K, V> node = table[index];
        if (node == null) {
            return null;
        }
        //开放地址法
        if (mode == 1) {
            //如果当前索引处node为空了并且还没有找到与键值匹配的关键字则跳出循环
            while (table[index] != null && !k.equals(table[index].getKey())) {
                index = (index + 1) % capacity;
                queryNum++;
            }
            return table[index] == null ? null : table[index].getValue();
        } else {//链式储存法
            while (node.next != null && !k.equals(node.getKey())) {
                node = node.next;
                queryNum++;
            }
            if (k.equals(node.getKey())) {
                return node.getValue();
            }
            return null;
        }
    }

    //获取index
    private int indexFor(int hash) {
        return hash % capacity;
    }

    //获取当前表中数量,1线性探测法,2链式法
    public int getNum(int type) {
        return type == 1 ? num : linkNodeNum;
    }

    //获取容量
    public int getCapacity() {
        return capacity;
    }

    //获取冲突次数
    public int getConflictsNum() {
        return conflictsNum;
    }

    /**
     * 更改处理冲突模式
     *
     * @param mode 1开放地址法，2链表储存法
     */
    public void setMode(int mode) {
        this.mode = mode;
    }

    //获取本次查询比较次数
    public int getQueryNum() {
        return queryNum;
    }

    //重新设置大小
    public void resize(int capacity) {
        //如果传入容量小于当前容量则不处理
        int size = this.capacity;
        if (capacity < this.capacity) {
            return;
        }
        conflictsNum = 0;
        num = 0;
        this.capacity = capacity;
        //数据迁移
        Node<K, V>[] oldTab = table;
        table = new Node[capacity];
        for (int i = 0; i < size; i++) {
            if (oldTab[i] != null) {
                put(oldTab[i].getKey(), oldTab[i].getValue());
            }
        }
    }

    //自定义节点类
    static class Node<K, V> {
        final K key;//键
        final int hash;//哈希值
        V value;//值
        Node<K, V> next;//链表处理冲突时用

        Node(K k, V v, int hash) {
            this.key = k;
            this.value = v;
            this.hash = hash;
            this.next = null;
        }

        public final K getKey() {
            return key;
        }

        public final V getValue() {
            return value;
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        @Override
        public final int hashCode() {
            return key.hashCode() ^ value.hashCode();
        }

        @Override
        public final boolean equals(Object o) {
            Node<?, ?> e = (Node<?, ?>) o;
            if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue()))
                return true;
            return false;
        }

        @Override
        public final String toString() {
            return key + "=" + value;
        }
    }
}

参考

1. 解决Hash冲突四种方法 (opens new window)
2. 百度百科 (opens new window)
3. 集合框架源码学习之HashMap(JDK1.8) (opens new window)