关于HashMap

    哈希表支持一种最有效的检索方法：散列。从根本上来说，一个哈希表包含一个数组，通过特殊的索引值(键)来访问数组中的元素。哈希表的主要思想是通过一个哈希函数，在所有可能的键与槽位之间建立一张映射表。哈希函数每次接受一个键将返回与键相对应的哈希编码或哈希值。键的数据类型可能多种多样，但哈希值的类型只能是整型。

    由于计算哈希值和在数组中进行索引都只消耗固定的时间，因此哈希表的最大亮点在于它是一种运行时间在常量级的检索方法。当哈希函数能够保证不同的键生成的哈希值互不相同时，就说哈希表能直接寻址想要的结果。但这只是理想的状态，在实际运用过程中，能够直接寻址结果的情况非常少。例如，一个电话邮件系统，通过8个字符组成的名字作为键，来哈希得到系统中的用户信息。如果我们想依赖直接寻址，那么这个哈希表将会有超过26^8=2.09×10^11个条目，而这些条目中的绝大多数都是无用的，因为大多数的字符组合都不是姓名。

    通过与各种各样的键相比，哈希表的条目数相应较少。因此，绝大多数哈希函数会将一些不同的键映射到表中相同的槽位上。当两个键映射到一个相同的槽位上时，它们就产生了冲突。一个好的哈希函数能最大限度地减少冲突，但冲突不可能完全消除，我们仍然要想办法处理这些冲突。

哈希表的结构（链式）：

    链式哈希表从根本上来说是由一组链表构成（数组+链表，链表是数组的元素）。每个链表都可以看做一个"桶"，我们将所有的元素通过散列的方式放到具体的不同的桶中(见下图)。插入元素时，首先将其键传入一个哈希函数(该过程称为哈希键)，函数通过散列的方式告知元素属于哪个"桶"，然后在相应的链表头插入元素。查找或删除元素时，用同样的方式先找到元素的"桶"，然后遍历相应的链表，直到发现我们想要查找的元素。因为每个"桶"都是一个链表，所以链式哈希表并不限制包含元素的个数。然而，如果表变得太大，它的性能将会降低。

如何存储：

    从上图我们可以发现哈希表是由数组+链表组成的，一个长度为16的数组中，每个元素存储的是一个链表的头结点。那么这些元素是按照什么样的规则存储到数组中呢。一般情况是，通过确定数组index——hashcode % table.length取模来获得，也就是元素的key的哈希值对数组长度取模得到。比如上述哈希表中，12%16=12,28%16=12,108%16=12,140%16=12。所以12、28、108以及140都存储在数组下标为12的位置。
　　HashMap其实也是一个线性的数组实现的,所以可以理解为其存储数据的容器就是一个线性数组。这可能让我们很不解，一个线性的数组怎么实现按键值对来存取数据呢？这里HashMap有做一些处理。

　　首先HashMap里面实现一个静态内部类Entry，其重要的属性有 key , value, next，从属性key,value我们就能很明显的看出来Entry就是HashMap键值对实现的一个基础bean，我们上面说到HashMap的基础就是一个线性数组，这个数组就是Entry[]，Map里面的内容都保存在Entry[]里面。

性能参数：

1.槽位：可插入的位置

2.初始容量：初始化时得到， public HashMap(int initialCapacity, float loadFactor) {...}，注意table初始大小并不是构造函数中的initialCapacity！！而是 initialCapacity的2的n次幂！！！！

3.尺寸：实际存放的数据个数

4.负载因子：尺寸/容量，默认值0.75，大于这个值时，认为时间/空间达到平衡，会再散列，即槽位加倍，重新分配位置

解决hash冲突：

1.开放定址法（线性探测再散列，二次探测再散列，伪随机探测再散列）

2.再哈希法

3.链地址法

4.建立一个公共溢出区

（Java中hashmap的解决办法就是采用的链地址法。）

（参考：https://blog.****.net/qq_35114086/article/details/70156793）