分析了哈希冲突

代码风水师 · 代码风水师 · commit 8ed789a7a769 · 2018-11-02T17:33:32.000+08:00
diff --git a/README.md b/README.md
@@ -8,7 +8,8 @@
 * 3.[集合框架 （第 03 篇） 精尽源码分析：ArrayList](https://github.com/about-cloud/JavaCore/blob/master/resource/markdown/collection/ArrayList.md)
 * 4.[集合框架 （第 04 篇） 精尽源码分析：LinkedList](https://github.com/about-cloud/JavaCore/blob/master/resource/markdown/collection/LinkedList.md)
 * 5.[集合框架 （第 05 篇） 精尽源码分析：Map<K, V>接口与其内部接口Entry<K,V>](https://github.com/about-cloud/JavaCore/blob/master/resource/markdown/collection/Map.Entry1.7v.md)
-* 6.[集合框架 （第 06 篇） 精尽源码分析：jdk1.7版 HashMap](https://github.com/about-cloud/JavaCore/blob/master/resource/markdown/collection/HashMap1.7v.md)
+* 6.[集合框架 （第 07 篇） 精尽源码分析：哈希冲突(哈希碰撞)与解决算法](https://github.com/about-cloud/JavaCore/blob/master/resource/markdown/collection/HashConflictsAndResolve.md)
+* 7.[集合框架 （第 06 篇） 精尽源码分析：jdk1.7版 HashMap](https://github.com/about-cloud/JavaCore/blob/master/resource/markdown/collection/HashMap1.7v.md)
 * 7.集合框架 （第 07 篇） 精尽源码分析：jdk1.7版 ConcurrentHashMap
 * 8.集合框架 （第 08 篇） 精尽源码分析：二叉树、平衡二叉树、二叉查找树、AVL树、红黑树 概念
 * 9.集合框架 （第 09 篇） 精尽源码分析：jdk1.8版 HashMap
diff --git a/resource/markdown/algorithm/ResolvingHashConflicts.md b/resource/markdown/algorithm/ResolvingHashConflicts.md
diff --git a/resource/markdown/collection/HashConflictsAndResolve.md b/resource/markdown/collection/HashConflictsAndResolve.md
@@ -0,0 +1,47 @@
+<h3 style="padding-bottom:6px; padding-left:20px; color:#ffffff; background-color:#E74C3C;">一、Hash冲突（哈希碰撞💥）</h3>
+
+#### 1.1、什么是冲突？
+
+![排椅](https://image.shutterstock.com/display_pic_with_logo/165962074/1085429735/stock-photo-colorful-plastic-resin-adirondack-chairs-in-a-row-1085429735.jpg)
+
+>  在一间教室里有一排座椅，这一排座椅线性排列对应的数据结构是 **数组**，数组的特点是可以根据下标(索引)快速🔜访问，通过下标(索引)访问的位置 `table[i]` 称为 **槽（slot）**，在伴随着 `哈希算法` 计算的槽称为 **哈希槽**。假设这排座椅共16个座位💺，编号从0,1,2…开始直到15。学校有很多学生，他们的编号也是从0,1,2…起始，有很多同学喜欢坐在一起，学校🏫为了让他们散列分开坐，采用 `模运算` 的方式。比如 1号同学的对座椅长度16模运算得1，那么你坐在1号位置，5号同学对座椅长度16模运算得5，那么他坐在5号位置，以此类推。1号座位已经被1号同学占用，新来的17号同学对16作模运算也得1，按照原来的算法，他也应该坐在1号，此时17号同学和1号同学的座位💺就 **冲突**。
+
+#### 1.2、哈希算法与哈希冲突
+
+> 实际上 **“编号”** 多种多样，如果它们共有某种特性、聚集密度增加，**冲突** 概率就有可能增大，为了防止这些 **项(元素)** 过于集中，而将它们按照某种算法 **散列** 分布，这种算法称为 **Hash算法**，翻译成**散列算法**，根据音译常翻译成**哈希算法**，通过 哈希算法 计算后的值称为**哈希码**或 **散列码**(HashCode)。假如 `1.1` 中学生的编号不是数字，而是其他字符组合，比如学生周星星的编号是 `ZXX9573` ，非 `Number` 类型的字符串是不能进行数学模运算的，即使能使用 `模运算` 也不能最大化的将他们散列开。所以使用 **哈希算法** 计算出 **哈希码**，然后根据模运算来决定它们该进入哪个 **槽**，这里的槽也称为 **哈希槽**。
+>
+> 这个通过 **散列** 方式存储元素的阵列容器称为 **散列表** (hashtable)，不过大多数人喜欢叫它**哈希表**。
+>
+> 如果跟据 **哈希算法** 计算得到的 **哈希码** 有多个相同的，那么模运算后得到的 **哈希槽** 也一定相同，也就产生了新的冲突，这种冲突称为 **哈希冲突(哈希碰撞💥)**。
+
+![哈希冲突()](https://images.pexels.com/photos/162943/aviary-pigeons-birds-feather-162943.jpeg?auto=compress&cs=tinysrgb&h=350)
+
+<h3 style="padding-bottom:6px; padding-left:20px; color:#ffffff; background-color:#E74C3C;">二、哈希冲突解决算法</h3>
+
+####  2.1、开放定址法（open addressing）
+
+> 一个元素与另一个元素关于某个地址(或槽)发生了冲突，将开放其他地址给此元素使用，这种算法称**开放定址法** 或 **开放地址法**。如何寻找适合的开放地址给此元素使用，这种寻找的过程或者技术称为**探测技术**。常见的 **“寻找技术”** 有如下几种：
+
+##### 线性探测
+
+> 接上面的故事，假设 1号座位已经有人，然后根据哈希算法计算出 `周星星` 应该落到 1号 座位，这时出现哈希冲突，然后按照线性方式探测下 1 个座位（哈希槽），如果2号座位（哈希槽）也有人，然后再按照线性方式探测下 1 个座位（哈希槽）... 以此类推。此种方式就是 **线性探测**。其中 “下 1 个” 指的是 **步长**，你也可以将步长定为2，那就是下2个。
+
+##### 二次探测
+
+>
+
+##### 伪随机探测
+
+> 伪随机探测的思路： 将线性探测的步长改为随机获取。
+
+####  2.2、再哈希法
+
+>
+
+####  2.3、:anchor:链地址法（链表法）:heavy_check_mark:
+
+>
+
+####  2.4、建立公共溢出区
+
+>
diff --git a/resource/markdown/collection/HashMap1.7v.md b/resource/markdown/collection/HashMap1.7v.md
@@ -10,11 +10,7 @@
 >
 >滴滴滴
 
-#### Hash冲突（哈希碰撞💥）
 
->在一间教室里有一排座椅，这一排座椅线性排列对应的数据结构是 **数组**，数组的特点是可以根据下标(索引)快速🔜访问，通过下标(索引)访问的位置 `table[i]` 称为 **槽**，在伴随着 `哈希算法` 计算的槽称为 **哈希槽**。假设这排座椅共16个座位💺，编号从0,1,2…开始直到15。学校有很多学生，他们的编号也是从0,1,2…起始，有很多同学喜欢坐在一起，学校🏫为了让他们散列分开坐，采用 `模运算` 的方式。比如 1号同学的对座椅长度16模运算得1，那么你坐在1号位置，5号同学对座椅长度16模运算得5，那么他坐在5号位置，以此类推。1号座位已经被1号同学占用，新来的17号同学对16作模运算也得1，按照原来的算法，他也应该坐在1号，此时17号同学和1号同学的座位💺就 **冲突**，在 `HashMap`中伴随着索引的由哈希算法计算的，此冲突又称 **哈希冲突(哈希碰撞💥)**。
-
-![哈希冲突(哈希碰撞)]()
 
 #### 解决哈希冲突的算法请参考另外一篇文章
 
diff --git a/resource/markdown/collection/Map.Entry1.7v.md b/resource/markdown/collection/Map.Entry1.7v.md
@@ -64,4 +64,4 @@ int hashCode();
 
 > :herb:合抱之木,生于毫末;:mount_fuji:九层之台,起于累土;:camel:千里之行,始于足下。
 >
-> :dart:再次提醒，请熟记这次基础方法。
+> :sound:再次提醒，请熟记这次基础方法。

Original file line number	Diff line number	Diff line change
`@@ -10,11 +10,7 @@`
`10`	`10`	`>`
`11`	`11`	`>滴滴滴`
`12`	`12`
`13`		`-#### Hash冲突（哈希碰撞💥）`
`14`	`13`
`15`		->在一间教室里有一排座椅，这一排座椅线性排列对应的数据结构是数组，数组的特点是可以根据下标(索引)快速🔜访问，通过下标(索引)访问的位置 `table[i]` 称为槽，在伴随着 `哈希算法` 计算的槽称为哈希槽。假设这排座椅共16个座位💺，编号从0,1,2…开始直到15。学校有很多学生，他们的编号也是从0,1,2…起始，有很多同学喜欢坐在一起，学校🏫为了让他们散列分开坐，采用 `模运算` 的方式。比如 1号同学的对座椅长度16模运算得1，那么你坐在1号位置，5号同学对座椅长度16模运算得5，那么他坐在5号位置，以此类推。1号座位已经被1号同学占用，新来的17号同学对16作模运算也得1，按照原来的算法，他也应该坐在1号，此时17号同学和1号同学的座位💺就冲突，在 `HashMap`中伴随着索引的由哈希算法计算的，此冲突又称哈希冲突(哈希碰撞💥)。
`16`		`-`
`17`		`-![哈希冲突(哈希碰撞)]()`
`18`	`14`
`19`	`15`	`#### 解决哈希冲突的算法请参考另外一篇文章`
`20`	`16`
Original file line number	Diff line number	Diff line change
`@@ -64,4 +64,4 @@ int hashCode();`
`64`	`64`
`65`	`65`	`> :herb:合抱之木,生于毫末;:mount_fuji:九层之台,起于累土;:camel:千里之行,始于足下。`
`66`	`66`	`>`
`67`		`-> :dart:再次提醒，请熟记这次基础方法。`
	`67`	`+> :sound:再次提醒，请熟记这次基础方法。`