在网上看了很多资料，找到一篇讲哈希表的，感觉非常不错，推荐直接去看原文，散列表的基本原理与实现
下面内容是我的一些为加深记忆而复制的笔记，并无新意。
散列表的工作过程：
- 首先我们使用散列函数将给定键转化为一个“数组的索引”，理想情况下，不同的key会被转为不同的索引，但在实际应用中我们会遇到不同的键转为相同的索引的情况，这种情况叫做碰撞。解决碰撞的方法我们后面会具体介绍。
- 得到了索引后，我们就可以像访问数组一样，通过这个索引访问到相应的键值对
散列表时间上的极端：数组，速度快，但需要连续内存。 散列表空间上的极端：链表，不需要连续内存空间，但只能顺序查找。 实际中，通过所谓的负载因子的神秘东西来调节权衡两者的比例。
散列表对哈希函数是有要求的：
- 速度快
- 散列值要均匀
- 安全性要求不高
不需要自己费神写哈希函数，这世界上已经有一堆可供选择的哈希函数，MD5，SHA1.... 关于哈希函数（哈希值：数值，字符串都支持），推荐一个 murmurhash Redis，Memcached，Cassandra，HBase，Lucene都用它。 在Java的实现，Guava的Hashing类里有，上面提到的Jedis，Cassandra里都有Util类。 Guava Hash类代码 murmurhash各版本简介
-
散列表的查找操作的时间复杂度为O(1)，插入操作的复杂度也为O(1)。当桶数为M，散列表中存储的键值对数目为N时，平均每个桶中的链表包含的结点数为N / M，因为，当我们查找一个键时，首先通过散列函数确定它所在的桶，这一步所需时间为O(1)；然后我们依次比较桶中结点的键与给定键，若相等则找到了指定键值对，这一步所需时间为O(N / M)。所以查找操作所需的时间为O(N / M)，而通常我们都能够保证N是M的常数倍，所以散列表的查找操作的时间复杂度为O(1)，同理我们也可以得到插入操作的复杂度也为O(1)。
-
负载因子oadFactor = maxSize / capacity，其中maxSize为支持存储的最大键值对数，而loadFactor和capacity（桶数：散列表容量，数值大小）都会在初始化时由用户指定或是由系统赋予默认值。
-
若负载因子较大，则查找时间会变长，但是空间使用会减小。
- 用大小为M的数组保存N个键值对，其中M > N，数组中的空位用于解决碰撞问题。
- 当发生碰撞时（一个键被散列到一个已经有键值对的数组位置），我们会检查数组的下一个位置，这个过程被称作线性探测。
- 数组已满的时候我们再向其中插入新键，会陷入无限循环之中。
- 既然是key-value，那么实现时候就要用两个数组同一位置上的元素共同确定一个散列表中的键值对。
对于碰撞的位置，继续通过key的equals 比较，来确定key正确的value值
HashMap其实也是一个线性的数组实现的,所以可以理解为其存储数据的容器就是一个线性数组。这可能让我们很不解，一个线性的数组怎么实现按键值对来存取数据呢？这里HashMap有做一些处理。 首先HashMap里面实现一个静态内部类Entry，其重要的属性有 key , value, next，从属性key,value我们就能很明显的看出来Entry就是HashMap键值对实现的一个基础bean，我们上面说到HashMap的基础就是一个线性数组，这个数组就是Entry[]，Map里面的内容都保存在Entry[]里面。