哈希表（散列表）

哈希表的原理：

在已知key的情况下，通过哈希函数f(),在数组中去寻找具体的值f(key)。
这里面f()称为哈希函数或者散列函数。
f(key)就是记录的存储位置。
通过散列计数将记录存储在一块连续的存储空间中，这块存储空间就是哈希表。

把key通过哈希函数转换成一个整型数字，然后将该数字对数组长度进行取余，取余结果当做数组的下标，把value存储在数组该下标所在的存储空间中。

使用哈希表查询的时候， 将key通过哈希函数转换成一个数字，然后算出数组下标，从而直接取出数组中的value值，充分利用了数组的快速定位功能。

比较好的哈希函数是time33算法。PHP的数组就是把这个作为哈希函数。

unsigned long hash(const char* key){
    unsigned long hash=0;
    for(int i=0;i<strlen(key);i++){
        hash = hash*33+str[i];
    }  
    return hash;
}

哈希冲突：

当两个key值不同，但是通过哈希函数得到的数值是一样的。此时就产生了哈希冲突。
即 key1≠key2,但是f(key1)=f(key2)。

数组的特点： 查询取值容易，但是插入删除费劲
链表的特点：查询取值费劲，插入删除简单。

哈希表有多种表现形式，其中最常用的就是拉链法，就是将数组和链表的功能相结合。
使用拉链法可以很好的去解决哈希冲突。 当两个不同的key获取了同一个数组下标，此时就在该数组存储空间中加一个指针，指向一个链表，然后将value存放在链表中。

一个好的哈希表应该满足两个特点：

1.尽量使关键字对应的记录均匀分布在哈希表中，这样可以在查询任意数值的时候都不会有过大的复杂度。（复杂度最高的一种哈希表就是，只有一个链表，这样哈希表就退化成了链表）
2.关键字极小的错误引起哈希表极大的变化。

哈希表的用途：

1.哈希主要用于信息加密，把一些不同长度的信息转化成杂乱的128位编码，这些编码值叫做hash值。
2.用于查找：之前的查找是在一堆元素中取出一个元素，然后和目标函数比对，不匹配缩小返回继续。现在使用哈希表，可以直接定位到相关内存中，大大缩短了查找耗时。

哈希表的优缺点：

优点：运行速度极快。
不考虑有序遍历数据，并且可以提前知道数据的大小。哈希表在速度和易用性上很牛逼。
缺点：它是基于数组的，数据创建后很难扩展，并且如果哈希表被填满后性能会下降的很快。程序员需要知道这个表的内存上限，这个很重要。并且需要定期将哈希表中的数据转移到比较大内存的表中，很费时。