Java架构师入门培训视频之HashMap

HashMap的底层实现原理

HashMap底层实现采用的是哈希表，一种非常重要的数据结构

哈希表的基本结构是:数组+链表

数组的特点：占用空间连续，寻址容易，查询速度快.但是，增加和删除的效率非常低

链表的特点：占用空间不连续，寻址困难，查询速度慢.但是，增加和删除的效率非常高

HashMap源码两个核心内容：Entry[]table就是HashMap的核心数组结构，也称之为位桶数组；Entry对象是一个单向链表的结构，里面存储了四个重要的属性hash,key,value,next

如下图：

HashMap存储数据的过程put(key,value)如下：

步骤如下：

1、获得key对象的hashcode–首先调用key对象的hashcode()方法，获得hashcode.

2、根据hashcode计算出hash值(要求在[0,数组长度-1]区间)，hashcode是一个整数，需要将它转化为[0,数组长度-1]的范围，要求转化后的hash值尽量均匀地分布在[0,数组长度-1]这个区间，减少"hash冲突".

一种极端简单和低下的算法:

hash值=hashcode/hashcode;

也就是说，hash值总是1，意味着键值对对象会存储到数组索引1位置，这样就形成一个非常长的链表，相当于每存储一个对象都会发生"hash冲突"，HashMap也退化为一个"链表".

一种简单和常用的算法是(相除取余算法):

hash值=hashcode%数组长度

这种算法可以让hash值均匀的分布在[0,数组长度-1]的区间，早期的HashTable就是采用这种算法。但是，这种算法由于使用了"除法"，效率低下。JDK后来改进了算法，首先约定数组长度必须为2的整数幂，这样采用位运算即可实现取余的效果：hash值=hashcode&(数组长度-1)

/**
 * 测试hash算法
 */public class TestHash {
	public static void main(String[] args) {
		int hashcode = 1111;
		int length = 16;//length为2的整数幂，则hashcode&(length-1)相当于hashcode%length
		myhash(hashcode, length);
	}
	public static void myhash(int hashcode,int length){
		//取余
		System.out.println(hashcode%length);
		//length为2的整数幂情况下，和取余的值一样
		System.out.println(hashcode&(length-1));
	}}

3、生成Entry对象

一个Entry对象包含四个部分，key对象、value对象、hash值、指向下一个Entry对象的引用，现在算出了hash值，下一个Entry对象的引用为null。

4、将Entry对象放到table数组中

如果本Entry对象对应的数组索引位置还没有放Entry对象，则直接将Entry对象存储进数组，如果对应索引位置已经有Entry对象，则将已有Entry对象的next指向本Entry对象，形成链表。

动力节点HashMap底层实现原理视频教程，快速掌握HashMap技术，强化自身技能：

课程学习目录

1.HashMap底层数据结构分析

2.JDK1.7中的HashMap底层实现分析

3.JDK1.8中的HashMap底层实现分析

4.HashMap的put操作源码分析（上）

5.HashMap的put操作源码分析（下）

6.HashMap的get操作源码分析

7.HashMap常见面试题分析

8.HashMap底层实现原理总结与展望

以上就是对“Java架构师入门培训视频之HashMap”的介绍，希望对大家有所帮助，还想学习更多关于Java的课程，可以关注动力节点官网Java视频教程，免费下载学习。