Hash

发表于 | 分类于 | 阅读次数:
字数统计: 3.2k | 阅读时长 ≈ 11

Hash表和Hash算法,HashMap

什么是哈希算法？

Hash，一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。（就是通过算法，将任意长度的输入转化为固定长度的输出。当然可能会有不同的输入经过算法运算后得到相同的输出。这叫做冲突）

这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

Hash算法特别的地方在于它是一种单向算法，用户可以通过hash算法对目标信息生成一段特定长度的唯一hash值，却不能通过这个hash值重新获得目标信息。因此Hash算法常用在不可还原的密码存储、信息完整性校验等。

常见的Hash算法有MD2、MD4、MD5、HAVAL、SHA

常见的Hash算法有加法Hash、位运算Hash、乘法Hash、除法Hash等

“将固定长度的输入转化为相同长度的输出”，下面是一个简单的哈希算法：

int Hash(int num)
{
    return (num*3)%7;
}

没错就是这么简单，将任意长度的数字输入转化为[0,7)之间的固定输出

String类的hashCode算法

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

使用 int 算法，这里 s[i] 是字符串的第 i 个字符，n 是字符串的长度，^ 表示求幂。（空字符串的哈希值为 0。）

哈希表

根据设定的哈希函数H(key)和所选中的处理冲突的方法，将一组关键字映射到一个有限的、地址连续的地址集(区间)上并以关键字在地址集中的“象”作为相应记录在表中的存储位置，这种表被称为哈希表。

数组的特点是：寻址容易，插入和删除困难；而链表的特点是：寻址困难，插入和删除容易。那么我们能不能综合两者的特性，做出一种寻址容易，插入删除也容易的数据结构？答案是肯定的，这就是的哈希表

HashMap

HashMap是基于Hashing（哈希）的原理，我们使用put(key,value)储存数据到HashMap中，使用get(key)从HashMap中得到此key对应的value。

HashMap底层基于Hash表（数组+链表）实现的。

VyZyL9.md.png

因为哈希算法的特点，固定长度的输入可以转化为特定长度的输出，这样必定会有不同的输入转化为同样的输出，所以相当于是一种映射关系：

哈希算法映射关系：

VylyUH.md.png

解释：

这种映射关系就像将一堆豆子一棒子打散到一个充满格子的框里，将这些豆子散列在固定的空间。

我们要用到数组的查询快速的优点，当然不能像真正的数组那样一个萝卜一个坑，所以我们使用“几个萝卜共用一个坑”这样的散列方法，而如果我们真的这样几个萝卜一个坑的话根本存不了，因为一个数组的位置只能放一个元素，加之另一个需求我们又想要增删快速，所以我们选择在数组的每个元素后面接一串链表，数组中存放链表首地址即可，这样同一个“坑”中的“萝卜”（元素）就能一一存放在数组中固定位置后面的链表节点中了。

当我们使用put(key,value)方法储存数据时，先对键key调用hashCode()方法，得到此key经过哈希算法运算后的哈希码值，这个哈希码值将作为数组中位置标识，可以理解为数组下标。

  • 情况1： 如果算出的位置目前没有任何元素存储，那么该元素可以直接添加到哈希表中。

  • 情况2：如果算出的位置目前已经存在其他的元素，那么还会调用该key的equals方法与这个位置上的元素的key进行比较，如果equals方法返回的是false，那么表示两个元素的key是不相同的，新来的元素允许被存储，则将新来的元素连接到链表末端；如果equals方法返回的是true，则表明两个key相同，那么此新来的元素被视为重复元素，则，此位置上的元素的key不变，value使用新来的元素的value。

验证：

package test;

import java.util.HashMap;

class User{
    int id;
    String name;
    public User(int id, String name) {
        this.id = id;
        this.name = name;
    }
    @Override
    public String toString() {
        return "User{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }
    @Override
    public int hashCode() {
        return this.id;
    }
    @Override
    public boolean equals(Object obj) {
        User u = (User)obj;
        return this.id == u.id;
    }
}
public class test {
    public static void main(String[] args) {
        HashMap<User,Integer> map = new HashMap();
        map.put(new User(111,"aaa"),123);
        map.put(new User(222,"bbb"),456);
        map.put(new User(333,"ccc"),789);
        map.put(new User(222,"ooo"),0);
        System.out.println(map);
        //{User{id=333, name='ccc'}=789, User{id=222, name='bbb'}=0, User{id=111, name='aaa'}=123}
        //输出的是 222,bbb 0  因为出现重复的key(key.hashCode相同key.equals也相同)时，
        // key使用原来的，value使用新来的
    }
}

疑惑点：

(为什么调用元素的key的hashCode方法，得到的哈希码值相同时还要调用key的equals方法再判断一次是

否相同呢？

因为不同输入经过哈希算法运算可能得到相同的哈希码值，“冲突”，再调用一次equals方法就

是判断两个key是否真的相同，如果真的相同，那么key不变，value使用新来的，如果不同就接着和下一

个节点比较，到最后都一直没有相同的元素就往链表末端

添加。

综上所述HashMap对重复元素的处理方法是：key不变，覆盖value)

当我们使用get(key)方法得到数组数据时，先对键key调用hashCode()方法，得到此key经过运算后的哈希码值，然后用此标识到数组中的某个位置查找，当此位置后面的链表中某个节点的元素的key和此key相同时，则返回此value。若不相同则顺着此链表通过pNext指针比对下一个key和此key是否相等。

Vy8U8s.md.png

大图：http://u6.gg/sEt97

注：图中并没有画出key的hashCode相同，equals也相同时，value覆盖的情况

我手写了一个简单的哈希表（也可以叫做HashMap），不过我没有储存(key,value)数据，为追求简单只是储存了简单的int类型数据（单key，没有value。为了突出HashMap的原理和数据结构，等有空会再把(key,value)补上），详情：https://github.com/hanhanhanxu/MyHashTable (使用C++编写)

这个是我自己写的java语言实现的HashMap，使用的数据结构也是数组+链表，这里面链表实现方式很特别，而且插入时是头插法，目前实现了put,get,toString方法：https://github.com/hanhanhanxu/MyHashMap

介绍下HashMap及其实现原理

HashMap是线程不安全
实现方式：
数组加链表的实现方式
数组中的每一项是一个链表，通过计算存入对象的key的hashCode来计算对象储存在数组中的位置，用链表来解决散列冲突，链表中的节点存储的是键值对，当出现重复的key时，key使用原来的，value使用新来的。

填充因子的作用

默认0.75 当hashmap的填充达到75%的时候，会进行扩容。当然这个值我们可以初始化。但如果没有什么特殊要求，不要进行更改。

hashmap的resize扩容机制

当hashmap中的元素越来越多的时候，碰撞的几率也就越来越高（因为数组的长度是固定的），所以为了提高查询的效率，就要对hashmap的数组进行扩容，数组扩容这个操作也会出现在ArrayList中，所以这是一个通用的操作，很多人对它的性能表示过怀疑，不过想想我们的“均摊”原理，就释然了，而在hashmap数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize。

那么hashmap什么时候进行扩容呢？当hashmap中的元素个数超过数组大小loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，也就是说，默认情况下，数组大小为16，那么当hashmap中元素个数超过160.75=12的时候，就把数组的大小扩展为216=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知hashmap中元素的个数，那么预设元素的个数能够有效的提高hashmap的性能。比如说，我们有1000个元素new HashMap(1000), 但是理论上来讲new HashMap(1024)更合适，不过上面annegu已经说过，即使是1000，hashmap也自动会将其设置为1024。 但是new HashMap(1024)还不是更合适的，因为0.751000 < 1000, 也就是说为了让0.75 * size > 1000, 我们必须这样new HashMap(2048)才最合适，既考虑了&的问题，也避免了resize的问题。

1.Hashmap在插入元素过多的时候需要进行Resize，
Resize的条件是 HashMap.Size >= Capacity LoadFactor。（默认：原来容量0.75）

2.Hashmap的Resize包含扩容和ReHash两个步骤，ReHash在并发的情况下可能会形成链表环。

  • 扩容
    创建一个新的Entry空数组，长度是原数组的2倍。

  • ReHash
    遍历原Entry数组，把所有的Entry重新Hash到新数组。为什么要重新Hash呢？因为长度扩大以后，Hash的规则也随之改变。

https://blog.csdn.net/HNUST_LIZEMING/article/details/89334204

为什么HashMap容量都是2的幂次方

因为得到索引时 可以通过按位与(&)操作来计算余数，比求模(%)更快，而且充分散列，减少碰撞

我们可以看到在hashmap中要找到某个元素，需要根据key的hash值来求得对应数组中的位置。如何计算这个位置就是hash算法。前面说过hashmap的数据结构是数组和链表的结合，所以我们当然希望这个hashmap里面的元素位置尽量的分布均匀些，尽量使得每个位置上的元素数量只有一个，那么当我们用hash算法求得这个位置的时候，马上就可以知道对应位置的元素就是我们要的，而不用再去遍历链表。

所以我们首先想到的就是把hashcode对数组长度取模运算，这样一来，元素的分布相对来说是比较均匀的。但是，“模”运算的消耗还是比较大的，能不能找一种更快速，消耗更小的方式那？

static int indexFor(int h, int length) {  
   return h & (length-1);  
   }

当容量是2^n时，h & (length -1) == h % length。

但这里让length为2的n次方，并不仅仅是要h & (length -1)的结果和h % length相等这么简单

使用与操作运算速度更快，而且如果不是2的n此方的话，h & (length -1)的就结果并不能够充分散列，有较大几率出现重复元素，，有的索引位置可能永远不会用到

参考链接:https://blog.csdn.net/gududedabai/article/details/85784161

参考链接:https://www.iteye.com/topic/539465

多线程hashMap进行put时出现死循环的情况

https://www.cnblogs.com/wfq9330/p/9023892.html

HashMap在JDK1.7和1.8种有什么变化

主要还是HashMap中链长度大于8时采取红黑树的结构存储。(1.7的时候是链表结构)
红黑树，除了添加，效率高于链表结构。

ConcurrentHashMap线程安全

分段锁思想来降低并发场景下的锁定发生频率

1.7 分段加锁

1.8 CAS自旋锁 乐观锁 并发度较高时，性能较一般

引入红黑树，解决哈希冲突时链表的顺序查找问题， 红黑树的启用条件与链表长度和Map总容量有关，默认链表>8 容量>64时转换为红黑树方式

insist,on the road
-------------本文结束感谢您的阅读-------------