哈希表基础

哈希表也称为散列表，是一种常见的数据结构，它提供了快速的插入操作和查找操作，无论哈希表总中有多少条数据，插入和查找的时间复杂度都是为O(1)，因为哈希表的查找速度非常快，所以在很多程序中都有使用哈希表。

其实哈希是一种思想，将我们的键值对中的键或者关键字与数组的下标所绑定，就比如说我们的学号就可以对应成数组的下标，不过学号对于数组来说可能太大了，我们需要一个函数去处理一下这个数字，这个转化的函数也就是哈希函数。

哈希函数完成了对于键或者关键字的转换，但具有三个条件：

• 哈希函数得到的散列值是一个非负整数，这个很好理解，因为数组的下标从0开始。
• 如果key1 = key2 那么hash（key1） = hash（key2）
• 如果key1 ！= key2 hash（key1）！= hash（key2）
  第一点：因为数组的下标是从0开始，所以哈希函数生成的哈希值也应该是非负数
  第二点：同一个key生成的哈希值应该是一样的，因为我们需要通过key查找哈希表中的数据
  第三点：看起来非常合理，但是两个不一样的值通过哈希函数之后可能才生相同的值，因为我们把巨大的空间转出成较小的数组空间时，不能保证每个数字都映射到数组空白处。所以这里就会才生冲突，在哈希表中我们称之为哈希冲突

哈希冲突以及解决

我们上面提到的第三点就是哈希冲突，不同的关键字经过hash转换后可能得到了相同的数组下标，如何解决hash冲突，常用的方法有两种，开放地址法以及链表法。

开放地址法

在开放地址法中，若数据不能直接存放在哈希函数计算出来的数组下标时，就需要寻找其他位置来存放。在开放地址法中有三种方式来寻找其他的位置，分别是「线性探测」、「二次探测」、「再哈希法」。

线性探测

在线性探测哈希表中，数据的插入是线性的查找空白单元，例如我们将数88经过哈希函数后得到的数组下标是16，但是在数组下标为16的地方已经存在元素，那么就找17,17还存在元素就找18，一直往下找，直到找到空白地方存放元素。
插入，查找，删除。
插入代码如下：

public void insert(Student student){
    int key = student.getKey();
    int hashVal = hash(key);
    while (array[hashVal] !=null && array[hashVal].getKey() !=-1){
        ++hashVal;
        // 如果超过数组大小，则从第一个开始找
        hashVal %=size;
    }
    array[hashVal] = student;
}

线性探测的查找类似于插入过程，首先我们根据查找的元素的关键字计算出对应的散列值，如何比较数组中下标为散列值的元素，判断是否为我们需要的，如果遍历到空的位置还没有找到，那么就说明不存在当前元素。

线性探测的删除我们也是根据之前的过程，找到对应的元素删除，并且在删除位置插入一个-1；

这样会带来一个问题，如何在线性探测哈希表中做了多次操作，会导致哈希表中充满了学号为-1的数据项，使的哈希表的效率下降，所以很多哈希表中没有提供删除操作，即使提供了删除操作的，也尽量少使用删除函数。

二次探测

在线性探测中，数据会发生聚集，一旦产生了聚集，它就会变得越来越大，我们查找数据的对应时间也会变长。

二次探测就是防止聚集的一种尝试，在线性探测中，如果哈希函数得到的原始下标是x,线性探测就是x+1,x+2,x+3…，以此类推，而在二次探测中，探测过程是x+1,x+4,x+9,x+16,x+25…,以此类推，到原始距离的步数平方。

但是二次聚集产生了新的聚集问题，如果我们在同一个映射位置插入多个元素，那么我们最后的步长会越来越大，非常吃容量，这个现象叫做二次聚集。
可见二次探测也不是一个好的方法，再哈希显然成为了更好的方法。

双哈希

双哈希是为了消除原始聚集和二次聚集问题，不管是线性探测还是二次探测，每次的探测步长都是固定的。双哈希是除了第一个哈希函数外再增加一个哈希函数用来根据关键字生成探测步长，这样即使第一个哈希函数映射到了数组的同一下标，但是探测步长不一样，这样就能够解决聚集的问题。
第二个哈希函数必须具备如下特点

和第一个哈希函数不一样
不能输出为0，因为步长为0，每次探测都是指向同一个位置，将进入死循环，经过试验得出stepSize = constant-(key%constant);形式的哈希函数效果非常好，constant是一个质数并且小于数组容量。

链表法

开发地址的思想是在当前hash表中再寻找一个空位解决冲突，而链表法则是每一个数组的位置对应着一条链表，我们只需要将冲突的数据插入到链表中，并不需要寻找空位。

哈希表的效率

在哈希表中执行插入和搜索操作都可以达到O(1)的时间复杂度，在没有哈希冲突的情况下，只需要使用一次哈希函数就可以插入一个新数据项或者查找到一个已经存在的数据项。

如果发生哈希冲突，插入和查找的时间跟探测长度成正比关系，探测长度取决于装载因子，装载因子是用来表示空位的多少
装载因子的计算公式：

装载因子 = 表中已存的元素 / 表的长度

装载因子越大，说明空闲位置越少，冲突越多，散列表的性能会下降。

iOS中的哈希表

上面是hash表的一些基础概念，在了解了概念我们可以来看看Apple设计了哪些哈希表的类，之前看Runtime的源码中就碰见了一些哈希表。

1. StripedMap类 （SideTables）

SideTables是个全局变量，它的类型是StripedMap类型。
StripedMap是一个只读哈希表，它的hashKey是对象地址addr，哈希函数是哈希函数是((addr >>4) ^ (addr >>9)) %StripeCount，Value是SideTable结构体。SideTable结构体中就包含引用计数表以及弱引用表，每个对象都有对应的SideTable，利用SideTables可以将对象信息分散到不同的SideTable中，提升查找效率。

2. weak_table_t

上面提到了每个sideTable中都包含弱引用表，weak_table就是一个全局的弱引用表，weak_table_t的Key是对象地址，hash函数如下：

static inline uint32_t ptr_hash(uint64_t key)

{

    key ^= key >>4;

    key *=0x8a970be7488fda55;

    key ^=__builtin_bswap64(key);

    return(uint32_t)key;

}

// 索引（下标） = 函数返回结果 & weak_table->mask

Value是weak_entry_t。weak_table_t可以通过对象指针快速找到对象存储的weak_entry_t。

weak_table_t可进行扩容与缩容。

当出现哈希冲突时，与weak_table_t配套的函数使用线性探测法查找。

每个weak_table_t中存储一堆对象的弱引用表。

3. weak_entry_t

weak_entry_t是一个特定情况才会出现的哈希表，苹果为了避免数量少的哈希表造成性能浪费，使用了共用体，如果weak指针小于4使用一个数组来保存对象的弱引用。
weak_entry_t的哈希Key是弱指针地址，value也是弱指针地址。哈希函数与weak_table_t相同。
每个weak_entry_t存储指向一个对象的所有弱指针地址（二级指针）。

4. RefcountMap

RefcountMap本质是DenseMap类按照指定模版typedef的类型。
RefcountMap的哈希Key是对象地址，Value是引用计数。

当value为0时，RefcountMap会自动清除这条记录。

当出现哈希冲突时，RefcountMap使用二次方探测法查找。

每个RefcountMap中存储一堆对象的引用计数。

5. StripedMapsDataLists

sDataLists是存储所有@synchronized锁的全局哈希表，key是@synchronized的参数。

6. StripedMap<spinlock_t> PropertyLocks

PropertyLocks是存储所有atomic锁的全局哈希表，key是属性生成的成员变量地址。

7. cache_t结构体

类对象的方法缓存cache_t使用哈希表存储bucket_t（sel+imp)，使用逆序线性探测（Index-1)解决哈希冲突。

cache_t扩容时会将所有方法缓存清空。

8. namedSelectors

static objc::ExplicitInitDenseSet<const char *> namedSelectors;

namedSelectors是个全局变量，存储所有的方法名SEL，内部结构是哈希表DenseMap。

9. AssociationsHashMap

typedef DenseMap<DisguisedPtr<objc_object>, ObjectAssociationMap> AssociationsHashMap;

AssociationsHashMap是AssociationsManager中存储所有关联对象的哈希表，内部结构是DenseMap。

10. [NSObject hash]

NSObject默认的hash方法是对象地址，即默认没有做优化。

uintptr_t_objc_rootHash(id obj)

{

    return (uintptr_t)obj;

}

常见的NSDictionary和NSSet内部就是哈希表，NSDictionary会使用Key作为哈希表的Key，NSSet使用元素作为Key。它们会对Key对象调用hash方法获得初步的哈希码，然后经过转变成为存储区域的索引（下标）。