hashmap的实现与优化-编程开发技术

《hashmap的实现与优化-编程开发技术》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、HashMap的实现与优化-编程开发技术HashMap的实现与优化原文出处：BlackSwiftHashMap的优化与实践本文是基于作者在github上的Android问题交流讨论坛提问而产生的一篇文章，也是口己早打算开坑的一篇文章。文章首先介绍了hashMap的一些基木知识,然后介绍了它在JDK8下的实现原理，最后着重介绍了几个面试中处理大数据的方法，文章比较长，我也写了好久，希望各位能够读完并发表意见。Android题交流讨论坛是开源达人Trinca在gitllub上组建的一个讨论组织，那里的捉问

2、与回答都非常靠谱。HashMap的复杂度如图是ArrayList/LinkedList/IlashMap三个数据结构的复杂度对比，口J以看川iHashMap整体上性能都非常不错，但是不稳定，为O(N/Buckets),N就是以数组中没有发生碰撞的元索。获取查找添加/删除空间ArrayList0(1)0(1)O(N)O(N)LinkedList0(N)0(N)0(1)0(N)HashMapO(N/Bucket_size)O(N/Bucket_size)O(N/Bucket_size)0(N)注：发生碰撞

3、实际上是非常稀少的，所以N/Bucket_size约等于1HashMap是对Array与Link的折衷处理，Array与Link可以说是两个速度方向的极端，Array注重于数据的获取，而处理修改(添加/删除)的效率非常低；Link曲于是每个对象都保持着下一个对象的指针，查找某个数据需要遍历之前所有的数据，所以效率比较低，而在修改操作中比较快。复杂度是如何考察的？对于数据结构，在时间上我们需要考察Acessing,Search,Deletion/Insertion的平均与最差的复杂度。在空间上，我们要考

4、虑维护这个数据结构所占用的内存空间。常见的数据结构与排序的复朵度都在这里HashMap的实现木文以JDK8的API实现进行分析1.什么是hash,什么是碰撞？•Hash：是一种信息摘要算法，它还叫做哈希，或者散列。我们平时使用的MD5,SHA1,SSL屮的公私钥验证都属于Hash算法，通过输入key进彳亍Hash计算，就可以获収key的HashCode(),比如我们通过校验MD5來验证文件的完整性。•碰撞：好的Hash算法可以出计算儿乎出独一无二的HashCode,如果出现了重复的hashCode,就

5、称作碰撞；>就算是MD5这样优秀的算法也会发生碰撞，即两个不同的key也有可能生成相同的MD5。2.HashMap中是如何实现写入与读取的？HashMap实现了Meip接口，保存着K-V这样的集合。我们以put操作为例2.1.对key进行Hash计算在JDK8屮，由于使用了红黑树来处理大的链表开销，所以hash这边可以更加省力了，只用计算hashCode并移动到低位就可以了staticfinalinthash(Objectkey){inth;//计算hashCode,并

6、无符号移动到低位return(key==null)?0:(h=key.hashCode())八(h>>>16);}下面给岀几个常用的哈希码的算法。1.Object类的hashCode.返回对彖的内存地址经过处理后的结构，由于每个对彖的内存地址都不一样，所以哈希码也不一样。这个是native方法，这个取决于JVM的设计,一般是某种地址的偏移。2.String类的hashCode.根据String类包含的？符串的内容，根据一种特殊算法返回哈希码，只要字符串的内容相同，返回的哈希码也相同。3.Integer

7、等包装类，返冋的哈希码就是Integer对象里所包含的那个整数的数值，例如Integeril=newInteger(100),i1.hashCode的值就是100。由此可见,2个一样大小的Integer对象，返回的哈希码也一样。4.int,char这样的基础类，它们不需要hashCode,如果需要存储时，将进行H动装箱操作，计算方法同上。2.2.获取到当前的位置计算了Hash,我们现在要把它插入数组中了i=(tab.length一1)&hash；通过位运算，确定了当前的位置，因为HashMap数组的大

8、小总是2,所以实际的运算就是(Oxfff・・・ff)&hash,这里的tab.length1相当丁个mask,滤掉了大于当丽长度位的hash,使每个i都能插入到数组屮。2.3.生成包装类这个对象是一个包装类，Node,内部有key,value,hash述有next,可以看出來它是一个链表。staticclassNodcimplementsMap.Entry〈K,V>{}finalinthash;finalKkey;Vvalue;No