11.哈希表

哈希表的原理：空间换时间，以一个足够大的数组来实现TreeMap，key作为索引，以达到增删改查操作的时间复杂度为O(1)

哈希表的关键元素：

• key：可以通过hash函数计算出table中的对应存放下标，hash冲突时通过equals函数对比是否是同一个key

• table：一个足够大的数组

• 哈希函数（散列函数）：时间复杂度为O(1)的函数，可以将key转化为table中的索引

• bucket(桶)：数组元素

  • 桶可能是链表结构，也可能是红黑树结构

  • 如果存入的元素哈希值相等

利用哈希函数生成key对应的index,根据index定位table中的bucket

稳定的哈希表必须同时实现equals和hashCode，因为默认的hashCode/equals是根据地址来计算索引，因为每次存放的地址不一样，所以计算出来的结果会一直变。索引的结果可能不同，同样的索引是否覆盖值也不同。

哈希冲突（哈希碰撞），不同的key经过哈希函数得出同一个值。解决方案：

• 开放定址法（Open Adressing）

  • 发现一个地址有值了，按照一定规则向其他地址探测，直到遇到空桶。这个规则可以是线性探测，即逐个下沿;平方探测，按平方数下沿搜索

• 再哈希法（Re-Hashing）

  • 设计多个哈希函数

• 链地址法（Separate Chaining）

  • 公用一个桶，通过链表将值串起来

  • 使用的是单向链表，因为存储新值，需要遍历之前的key，看是需要替换还是需要新增

哈希函数的工作原理：通过函数计算出一个整数，再用整数%table的长度，这样必然得到一个table的下标

为了提高工作效率，可以用&运算取代%，前提是桶数组（table）的长度设计为2ⁿ

index = Hash(key) & (table.length - 1)

2⁵-1 = 100000 - 1 = 011111

• 良好的哈希函数：哈希值更加均匀的分布，减少哈希冲突，提升哈希表性能

• 不同类型的Key值，计算的方式也不一样，原则上尽量让元素的每一部分都参与计算

  • int：可以直接作为哈希值返回

  • 浮点数：获得浮点数内存中的二进制表示如1011011，将二进制表示作为整数值91返回。

  • long、double：

// double先转成long
- (int)hash_Code:(long)longValue {
  // 以下图为例，&运算结果变成取后面部分，|运算结果为取前面部分，不能充分结合两个部分进行计算。
    return (int)(longValue^(longValue>>32));
}

* 字符串：

Jack = j x n³+a x n²+c x n¹+k x n⁰ = [(j x n + a) x n + c] x n + k

一般情况下 n = 31,因为31是一个奇素数，31 x i 可以优化成 （i << 5）- i

// jack = 3254239 
- (NSInteger)getHashCodeWith:(NSString*)str {
    NSInteger length = str.length;
    NSInteger index = 0;
    NSInteger hashCode = 0;
    NSInteger n = 31;
    if (length >= 2) {
        NSString *num1Str = [str substringWithRange:NSMakeRange(0, 1)];
        NSInteger num1 = [num1Str characterAtIndex:0];
        NSString *num2Str = [str substringWithRange:NSMakeRange(1, 1)];
        NSInteger num2 = [num2Str characterAtIndex:0];
        hashCode = num1 * n + num2;
        
        str = [str substringFromIndex:2];
    }
    // 如果后面还有数，那么 *n + 后面的数，进入下一个循环
    while (str.length > 0) {
        NSString *num1Str = [str substringWithRange:NSMakeRange(0, 1)];
        NSInteger num1 = [num1Str characterAtIndex:0];
        hashCode = hashCode * n + num1;
        index += 1;
        str = [str substringFromIndex:1];
    }
    return hashCode;
}

自定义对象的哈希函数

根据对象的每个属性的类型，获取各自的哈希值，将这些哈希值按字符串的哈希值获取方式来组合生成新的哈希值：

（（属性1的哈希值 * 31 + 属性2的哈希值）* 31 + 属性3的哈希值） * 31 + 属性4.....以此类推