HashMap分析
2019-11-09 15:53:22
供稿：网友
一 .概况1.概念和相关需要了解的基础知识点1.1 HashMap也是我们使用非常多的Collection，它是基于哈希表(散列表)的 Map 接口的实现，以key-value的形式存在。在HashMap中，key-value总是会当做一个整体来处理，系统会根据hash算法来来计算key-value的存储位置，我们总是可以通过key快速地存、取value。HashMap的底层实现还是数组（table）。1.2 散列表散列地址：数组的索引角标（table中的index）散列函数：散列表算法希望能尽量做到不经过任何比较，通过一次存取就能得到所查找的数据元素，因而必须要在数据元素的存储位置和它的关键字（可用key表示）之间建立一个确定的对应关系，使每个关键字和散列表中一个唯一的存储位置相对应。因此在查找时，只要根据这个对应关系找到给定关键字在散列表中的位置即可。这种对应关系被称为散列函数(可用h(key)表示)。1.3常用的散列函数有（1）、直接定址法取关键字或关键字的某个线性函数值为散列地址，即：h(key) = key 或 h(key) = a * key + b其中a和b为常数。（2）、数字分析法（3）、平方取值法取关键字平方后的中间几位为散列地址。（4）、折叠法将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为散列地址。（5）、除留余数法取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址，即： h(key) = key MOD p p ≤ m（6）、随机数法选择一个随机函数，取关键字的随机函数值为它的散列地址，即：h(key) = random(key)其中random为随机函数。1.4、处理冲突1.4.1产生冲突的原因对不同的关键字可能得到同一散列地址，即key1 ≠ key2，而h(key1)= h(key2)，这种现象称为冲突。具有相同函数值的关键字对该散列函数来说称作同义词。在一般情况下，散列函数是一个压缩映像，这就不可避免地会产生冲突，因此，在创建散列表时不仅要设定一个好的散列函数，而且还要设定一种处理冲突的方法。1.4.2解决冲突的方法（1）、开放定址法hi =(h(key) + di) MOD m i =1,2,…,k(k ≤ m-1)其中，h(key)为散列函数，m为散列表表长，di为增量序列，可有下列三种取法：1)、di = 1,2,3,…,m-1，称线性探测再散列；2）、di = 12,-12,22,-22,32,…,±k2 (k ≤m/2)，称二次探测再散列；3）、di = 伪随机数序列，称伪随机探测再散列。（2）、再散列法hi = rhi(key) i = 1,2,…,krhi均是不同的散列函数。（3）、链地址法将所有关键字为同义词的数据元素存储在同一线性链表中。假设某散列函数产生的散列地址在区间[0,m-1]上，则设立一个指针型向量void *vec[m],其每个分量的初始状态都是空指针。凡散列地址为i的数据元素都插入到头指针为vec[i]的链表中。在链表中的插入位置可以在表头或表尾，也可以在表的中间，以保持同义词在同一线性链表中按关键字有序排列。（4）、建立一个公共溢出区二.HashMap的详细说明HashMap提供了三个构造函数：HashMap()：构造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的空 HashMap。HashMap(int initialCapacity)：构造一个带指定初始容量和默认加载因子 (0.75) 的空 HashMap。HashMap(int initialCapacity, float loadFactor)：构造一个带指定初始容量和加载因子的空 HashMap。在这里提到了两个参数：初始容量，加载因子。这两个参数是影响HashMap性能的重要参数，其中容量表示哈希表中桶的数量，初始容量是创建哈希表时的容量，加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度，它衡量的是一个散列表的空间的使用程度，负载因子越大表示散列表的装填程度越高，反之愈小。对于使用链表法的散列表来说，查找一个元素的平均时间是O(1+a)，因此如果负载因子越大，对空间的利用更充分，然而后果是查找效率的降低；如果负载因子太小，那么散列表的数据将过于稀疏，对空间造成严重浪费。系统默认负载因子为0.75，一般情况下我们是无需修改的。HashMap是一种支持快速存取的数据结构，要了解它的性能必须要了解它的数据结构。其内部的数据结构就是哈希表，也就是散列表而相关的特性在上面已经都列出了，这里做一个总结：（1）HashMap内部存储使用的是哈希表（散列表），底层是数组（2）HashMap使用的散列表中散列函数为：直接定地址法（key的hashcode）；解决冲突用的链地址法（3）默认初始容量 (16) 和默认加载因子 (0.75)（4）value作为key值的“附带物“保存（5）数据在hashmap中的存，取过程：存：a.根据key的hashcode得到哈希值，再经int hash = hash(key.hashCode())得到其在table数组中的索引b.判断索引位上有没有数据，没有就直接存；有看key是不是相同，若相同则新value值取代老value值，若不同则以链表的方式存入取：就是存的反向过程，没有就只能返回null（6）对于HashMap的table而言，数据分布均匀问题：最好每项都只有一个元素，这样就可以直接找到，不能太紧也不能太松，太紧会导致查询速度慢，太松则浪费空间.具体的分析参考：http://www.cnblogs.com/chenssy/p/3521565.html中的分析 参考：HashMap：http://www.cnblogs.com/chenssy/p/3521565.html 散列表：http://blog.csdn.net/npy_lp/article/details/7390378
