顺序查找

二分查找

也称「折半查找」。前提是查找内容属有顺序的。

可以使用qsort函数实现快速排序。
qsort(数组起始地址，数组中元素个数，数组中每个元素占用空间大小，比较规则); 中九85‘

哈希查找

『哈希』其实就是「散列」。

哈希函数

是一个把查找表中的关键字映射成该关键字对应地址的函数。(这里的地址可以是数组的下标、索引或内存地址等)

业界常用的哈希函数：

int hash(const char * kye){
    int h =0,g;
    while(*key){
        h=(h << 4) + *key++;
        g = h & 0xf0000000;
        if(g){
            h ^= g >> 24;
        }
        h &= ~g;
    }
    return h % MaxKey; // MaxKey 是自己定义的数组下标最大限制。
}

冲突与处理

哈希(散列)冲突，即指散列函数可能会把两个或两个以上的不同关键字映射到同一地址。

冲突处理

• 链表法
• 再散列法

哈希表

根据关键字而直接进行访问的数据结构，即散列表建立了关键字和存储地址之间的一种直接映射关系。理想情况下，对散列表进行查找的时间复杂度为O(1),与表中的元素个数无关。