哈希表 散列表 hash table 他们是什么?
hash table
中文叫做散列表或者是哈希表,其实是一个意思
原文:https://github.com/googege/AMAC/edit/master/basic/17/README.md
go 语言中的map用到的就是hash table的思想，思想本身就是映射，一个萝卜一个坑，可以快速找到我们要找的内容，并且和数组不同我们可以指定不同的k，
在数组中我们只能是数但是在哈希表中我们可以用字符串等等数据来指定k。
hash表是使用k通过哈希函数然后对应相应数组中的下表然后再通过下表找到数据的过程，所以说查找的时间复杂度才是O(1)
所以说底层的数据还是数组，只不过我们这里的k可以使任何的数据然后这个任何数据通过某种函数转化为数组的下标。这些下标和key值是一一对应的。
所以说白了 计算机里的数据结构最最最根本的就两种 1 数组 2 指针对象
利用数组的 比如 1 数组 2 切片 3 栈 4 队列 5 哈希表 。利用指针的 1 链表 跳表 树 图 ...
所以说在哈希表中找到k和底层数组下标的这个函数就至关重要，因为除了这个就是数组了嘛，对吧，所以说重点就是哈希函数（映射函数）
hash 函数
大概就是这样的 散列值 = Hash(key) 也就是说这个函数就是key和数组下标的转换，这种函数有三点要注意
-
散列值一定是非负整数 这一点也容易理解，如果不是整数你也没办法再数组中找到它的位置
-
如果 key1 == key2 那么 hash(key1) == hash(key2)
-
如果key1 != key2 那么 hash(key1) != hash(key2)
前面两点都容易实现，也没什么可探讨的，但是第三点不容易，因为你计算出的值很不一定，很有可能key不同但是结果是一眼的。
目前的MD5或者等等算法也不能避免出现这种 “散列冲突” 就是key不一样但是非常有可能计算出的结果是一样的。
举个例子 你使用一种算法 那么key相同 就跟路是一样的走的过程肯定是一样的嘛，但是你走不同的小路 有可能最后走到了一条大路，也就是出现了相同的结果
这种就是 散列冲突
如何解决散列冲突？
- 寻址法 简单的说就是发现生成的那个整数被占用了，然后就往后找找到一个空闲的就住进去 包括这种方法 线性法 二次探测法 和多重探测法，
线性就是傻傻的一个一个往后找，二次探测就是第一次是1 第二次是2 第三次是4 第三次是 8 这种方式，多重就是搞几个函数，就不行了都不行？
大概就是这几种方法，但是如果数组中的数据真的快满了那么这几种都不好使，性能就不是O(1)了，甚至能退化成O(n)因为你要一个一个的往后找对吧，
这里提出一个概念 装载因子 = 装了的/总共的 越大证明散列的性能越差。
不过很多编程语言都会让散列表动态的扩容，例如go的map就是自动扩容的，所以你装的多，那么底层的数组就大就行了，这里我们也要看清楚
扩容是扩容，但是需要数据的复制，所以扩容的时候非常的消耗，所以尽量按照len就设置一个map的len，这是最好的优化。，
- 链表法，也就是将这个数组的地方我们不是储存的value值了，而是储存的一个链表，就是算出来是这个值的统统放到这个桶里，然后再进行选择。
但是时间复杂度增加的时候还是O(1)因为毕竟找到桶然后直接丢到最后即可，但是查找或者是删除的时候就需要我们遍历这个链表，如果链表非常长的
时候，那么就要耗费了不少时间复杂度了 基本上平均数是 O(N/桶的个数)
对于这种第二种方法，我们可以使用某些优化方法，例如说 将这个链表换成更加高效的数据结构，例如跳表或者是红黑树这样就从n转变成了logn
其实要小很多了。
动态扩容
还记得go语言中的map吗，你可以不指定len的长度，你随意的去装载数据也可以，go这里就是采用的动态扩容，不扩容就那点容量时间复杂度马上就变成了O(n)
动态扩容的时候我们需要1 重新计算哈希值 2 需要将旧的数据复制到新的内存里，那么将会耗费大量的时间
解决办法就是 当扩容的时候并不要复制数据，而是在新插入数据的时候拿出来一个数据进行复制操作，然后往复，查找的时候也简单，先查新的没有再查老的。
什么时候完毕了，直接gc掉那个旧的内存地址就行了。
设计散列函数的几点要求
-
设定阀值，当达到了这个值以后就动态扩容
-
要求有良好的散列冲突解决方法 或者 寻址 或者 chainning 总之在最差的几率下不能让性能下降过多。
底层数组到底储存的是什么？
我们使用k 通过 hash function然后算出来的是一个正整数 这个数叫做散列值然后找到这个数组，或者是值或者是 链表然后将 键值对
储存进去，所以当我们查找的时候我们就可以比较整个链表中的k-v值，其实是比较的是k值，只要k值正确，那么返回出v值即可。
散列表和链表为什么经常一起使用，他们之间到底是什么练习
首先 LRU 的整体实现原理就是 ：我们先保证一个已经知道容量的链表，先查看一下我们要加入的数据在不在链表中，在，就把这个链表数据从现在这个地方
送到最前面或者是最后面（相对应的删除的时候也是最后面或者是最前面），没有数据直接装填到最前面，然后如果满了，就把最后面的那个删除即可，
这一系列需要 1 查找 2 删除 3 插入 使用链表 查找的时间复杂度是n 为此使用链表+哈希表（链表实现）
每次的查找使用哈希表o（1）查找到即可，然后将这个模块搬移到最后，就是插入，插入的话也是o1（使用哈希表）
删除的话通过哈希表找到某个值然后再删除也是o（1）所以这个整个的过程就变成了O(1)
这里有两组链表 其中node节点都是一个 但是 这个节点 有三个指针 其中一个 是作为哈希表中的链表存在的，另外两个是作为 LRU算法中的双链表而
存在，所以这个节点一共有三个节点存在，
