hash表--hashMap

Hash表

（hash table , 也叫散列表），是根据关键码值而直接进行访问的数据结构，

  它通过把关键码值映射到表中一个位置来访问记录，以加快查找速度。

  关键码值(key value)也可以当作key的hash值

  这个映射函数叫做散列函数

  存放记录的数组叫做散列表

  元素 某个关系R 数组   

将元素按照关系R运算后找到数组中对应的储存位置

记录的存储位置=f(关键字)

装填因子： 元素长度/数组长度

优点：查找，插入，删除只需要接近常量的时间O(1),事件上就是几条机器指令。hash表在速度和易用性方面是无与伦比的

缺点：基于数组的，数组创建后难于拓展，当hash表被基本填满后，性能下降非常严重，所以要求预先清楚存储多少数据

举例  HashMap

hash表-拉链法

简单源码解析：

    static final float DEFAULT_LOAD_FACTOR = 0.75f;  //默认的扩容因子

    static final int DEFAULT_INITIAL_CAPACITY = 4; //默认的大小，因为扩容不易，所以请估计好大小，初始化时传入

我们举例看一下添加元素：

int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key); // hash函数，得到hash值

下面通过hash函数找到其在散列表中的位置，然后循环散列表对应位置处对应的链表，通过if判断看有没有保存过此key，如果有就替换掉value，如果没有继续下面的 

addEntry(hash, key, value, i); //添加元素

如果长度不够 ，扩容，然后再添加上元素，就不再一一详细叙述了。