Hash 与 Hash表 与 HashCode、HashMap 数据结构、HashMap 的容量

Hash 与 Hash表 与 HashCode

什么是 Hash

• 哈希 (hash) 简单的理解就是将任意长度的输入通过散列算法转换成固定长度的输出，这个输出一般称之为 散列码 或 哈希值
• 通过输出的结果来访问地址的数据结构

Hash 表

• hash 表也称散列表（Hash table）
• 哈希表是一种根据关键码去寻找值的数据映射结构
• 也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度

HashCode

• HashCode 通过 hash 函数计算得到，HashCode 就是在 hash 表中有对应的位置
• HashCode 的存在主要是为了查找的快捷性，HashCode 是用来在散列存储结构中确定对象的存储地址的
• Java 语言中，Object 对象有个特殊的方法：hashcode()
• hashcode() 表示的是 JVM 虚拟机为这个 Object 对象分配的一个 int 类型的数值

HashMap 数据结构

HashMap 的数据结构主要分为以下两个版本的改动。

JDK 1.7

• 采用的是 数组 + 链表

JDK 1.8

• 采用的是 数组 + 链表 + 红黑树

HashMap 的容量

• 指的是数组的大小
• 如果不指定初始容量，默认大小是 1<<4，也就是 2 的 4 次方，也就是 16 的大小
• DEFAULT_INITIAL_CAPACITY = 1 << 4;，Hash 表默认的初始容量

img

HashTable 数据结构

在 JDK1.7 当中 HashTable 数据结构为 数组 + 链表，假定现在有一个 HashMap 内容如下。

/**
 * @author yby6
 **/
public class HashTest {
    public static void main(String[] args) {
        Map<String, Object> peopleMap = new HashMap<>(16);

        peopleMap.put("张三", "zs");
        peopleMap.put("李四", "ls");
        peopleMap.put("王五", "ww");
        peopleMap.put("赵六", "zl");
        peopleMap.put("周七", "zq");
        peopleMap.put("郑八", "zb");
    }
}

上面的代码我们先画一个简略的示意图，进行分析如下。

img

为什么不直接把 key 和 value 放到数组当中，我们想要把数据放到数组当中，如果按角标的顺序进行存放，可以这样存放如下图。

img

但是这样放在取数据的时候，我们取的时候就比较麻烦了，因为我们取的时候是根据 key 值来进行取的，如果直接这样放，要先通过遍历的方式来查找，找到对应的位置，才能取到对应的数据。

🐤那么这个时候数据该如何存到数组当中呢？其实还是有方式的，在 MashMap 中的 key 必须是引用数据类型，引用数据类型都会有一个 HashCode 值，这个值是 JVM 虚拟机为这个 Object 对象分配的一个 int 类型的数值，把 HashCode 的值放到数组当中去，但是 HashCode 的值是不确定的有可能比 16 要大很多，可以采用 key.hashcode % 16，取模之后，得到的结果就是 1-15 之间，在 HashMap 中并不是直接使用取模的方式控制在 1-15 之间，是采用位运算的方式，位运算的效率要高于取模，位运算效率最高，取模效率最差。

🐱‍💻源码分析

img

img

img

img

通过 异常 和 与运算，让得到的 hash 值更加散列，减少 hash 的 碰撞，如下的方法我只是给出来进行参考用，就是解释一下为什么它这样就可以保证计算的 hash 值在指定的范围之间。

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

img

取模之后得到一个结果，这个结果正好对应 1-15 之间的位置，假设 key 为张三 HashCode 取模的结果为 2，就把张三对应的 key, value 放到数组中角标为 2 的位置存储。

img

最后

本期结束咱们下次再见👋~

🌊 关注我不迷路，如果本篇文章对你有所帮助，或者你有什么疑问，欢迎在评论区留言，我一般看到都会回复的。大家点赞支持一下哟~ 💗

我正在参与2023腾讯技术创作特训营第三期有奖征文，组队打卡瓜分大奖！