hashmap存多少条数据_HashMap源码解析，扩容机制及其思考

1.概述

HashMap是日常java开发中常用的类之一&＃xff0c;是java设计中非常经典的一个类&＃xff0c;它巧妙的设计思想与实现&＃xff0c;还有涉及到的数据结构和算法&＃xff0c;&＃xff0c;值得我们去深入的学习。

简单来说&＃xff0c;HashMap就是一个散列表&＃xff0c;是基于哈希表的Map接口实现&＃xff0c;它存储的内容是键值对 (key-value) 映射&＃xff0c;并且键值允许为null(键的话只允许一个为null)。

1.1 注意事项

①根据键的hashCode存储数据。(String&＃xff0c;和Integer、Long、Double这样的包装类都重写了hashCode方法&＃xff0c;String比较特殊根据ascil码还有自己的算法计算&＃xff0c;Double做位移运算【具体看源码的hashcode实现】&＃xff0c;Integer&＃xff0c;Long包装类则是自身大小int值)&＃xff0c;

HashMap中的结构不能有基本类型&＃xff0c;一方面是基本类型没有hashCode方法&＃xff0c;还有HashMap是泛型结构&＃xff0c;泛型要求包容对象类型&＃xff0c;而基本类型在java中不属于对象。

②HashMap的存储单位是Node,可以认作为节点。

③Hashmap中的扩容的个数是针对size(内部元素(节点)总个数)&＃xff0c;而不是数组的个数。比如说初始容量为16&＃xff0c;第十三个节点put进来&＃xff0c;不管前面十二个占的数组位置如何&＃xff0c;就开始扩容。

1.2 hashmap几个特征

2.一些概念

2.1.位运算

位运算是对整数在内存中的二进制位进行操作。

在java中 >> 表示右移 若该数为正&＃xff0c;则高位补0&＃xff0c;若为负数&＃xff0c;高位补1

<

例如20的二进制为0001 0100 20>>2为 0101 0000 结果为5(左高右低)

20<<2 为 0101 0000 则为80

java中>>>和>>的区别

>>>表示无符号右移&＃xff0c;也叫逻辑右移。不管数字是正数还是负数&＃xff0c;高位都是补0

在hashMap源码中有很多使用位运算的地方。例如:

//之所以用1 <<4不直接用16&＃xff0c;0000 0001 -> 0001 0000 则为16&＃xff0c;如果用16的话最后其实也是要转换成0和1这样的二进制&＃xff0c;位运算的计算在计算机中是非常快的&＃xff0c;直接用位运算表示大小以二进制形式去运行&＃xff0c;在jvm中效率更高。static final int DEFAULT_INITIAL_CAPACITY &＃61; 1 <<4; //初始化容量

注意:左移没有<<

2.2 位运算符-(与(&)、非(~)、,或(|)、异或(^))

①与运算(&)

我们都知道&在java中表示与操作&表示按位与&＃xff0c;这里的位是指二进制位。都为1才为真(1),否则结果为0&＃xff0c;举个简单的例子

System.out.println(9 & 8); //1&1&＃61;1&＃xff0c;1&0 0&1 0&0都&＃61;0&＃xff0c;因此1001 1000 -> 1000 输出为8

②非运算(~)

源码 -> 取反 -> 反码 -> 加1 -> 补码 -> 取反 -> 按位非值

在Java中&＃xff0c;所有数据的表示方法都是以补码的形式表示&＃xff0c;如果没有特殊说明&＃xff0c;Java中的数据类型默认是int,int数据类型的长度是8位&＃xff0c;一位是四个字节&＃xff0c;就是32字节&＃xff0c;32bit.

例如5的二进制为0101

补码后为 00000000 00000000 00000000 00000101

取反后为 11111111 11111111 11111111 11111010

【因为高位为1 所以源码为负数&＃xff0c;负数的补码是其绝对值源码取反&＃xff0c;末尾再加1】

所以反着来末尾减1得到反码然后再取负数

末位减1&＃xff1a;11111111 11111111 11111111 11111001

【后八位前面4位不动 后面 减1 1010减1 相当于 10-1为9 后四位就是 1001 】

取反后再负数&＃xff1a; 00000000 00000000 00000000 00000110 为-6

System.out.println(~ 5); //输出-6

③或运算(|)

只要有一个为1&＃xff0c;结果为1&＃xff0c;否则都为0

System.out.println(5 | 15); //输出为15&＃xff0c;0101或上1111,结果为1111

④异或运算(^)

相同为0(假)&＃xff0c;不同为真(1)

System.out.println(5 ^ 15); //输出10 0101异或1111结果为1010

2.3 hashcode

hash意为散列&＃xff0c;hashcode是jdk根据对象的地址或者字符串或者数字算出来的int类型的数值&＃xff0c;顶级父类Object类中含hashCode方法(native本地方法&＃xff0c;是根据地址来计算值)&＃xff0c;有一些类会重写该方法&＃xff0c;比如String类。

重写的原因。为了保证一致性&＃xff0c;如果对象的equals方法被重写&＃xff0c;那么对象的hashcode()也尽量重写。

简单来说 就是hashcode()和equals()需保持一致性&＃xff0c;如果equals方法返回true&＃xff0c;那么两个对象的hashCode 返回也必须一样。

否则可能会出现这种情况。

假设一个类重写了equals方法&＃xff0c;其相等条件为属性相等就返回true&＃xff0c;如果不重写hashcode方法&＃xff0c;那么依据就是Object的依据比较两个对象内存地址&＃xff0c;则必然不相等&＃xff0c;这就出现了equals方法相等但是hashcode不等的情况&＃xff0c;这不符合hashcode的规则&＃xff0c;这种情况可能会导致一系列的问题。

因此&＃xff0c;在hashMap中&＃xff0c;key如果使用了自定义的类&＃xff0c;最好要合理的重写Object类的equals和hashcode方法。

2.4 哈希桶

哈希桶的概念比较模糊&＃xff0c;个人理解是数组表中一块区域结果下面的单向链表组成的&＃xff0c;在hashmap中&＃xff0c;这个单向链表的头部是所在数组上第一个元素&＃xff0c;单向链表如果过长超过8&＃xff0c;那么这个"桶"就可能变成了红黑树(前提是数组长度达到64)。

2.5 hash函数

在程序设定中&＃xff0c;把一个对象通过某种算法或者说转换机制对应到一个整形。

主要用于解决冲突的。

2.6 哈希表

也称为散列表&＃xff0c;这也是一种数据结构&＃xff0c;可以根据对象产生一个为整数的散列码(hashCode)。

hash冲突

HashMap之所以有那么快的查询速度&＃xff0c;是因为他的底层是由数组实现&＃xff0c;通过key计算散列码(hashCode)决定存储的位置&＃xff0c;HashMap中通过key的hashCode来计算hash值&＃xff0c;只要hashCode相同&＃xff0c;hash值也一样&＃xff0c;但是可能存在存的对象多了&＃xff0c;不同对象计算出的hash值相同&＃xff0c;这就是hash冲突。

举个例子

HashMap map &＃61; new HashMap();map.put("Aa