数据结构篇 (3) 查找

本文主要介绍三种常用的查找算法,并侧重介绍Hash查找相关的知识点。

1.常用的三种查找算法
(1) 顺序查找:O(n),当序列中的元素没有任何规律的时候,按照元素的顺序遍历查找

def sequential_search(a_list, item):
    pos = 0
    found = False
    while pos < len(a_list) and not found:
        if a_list[pos] == item:
            found = True
        else:
            pos = pos+1
    return found

test_list = [1, 2, 32, 8, 17, 19, 42, 13, 0]
print(sequential_search(test_list, 3))
print(sequential_search(test_list, 13))

(2) 二分查找:O(lgn),当序列中的元素是有序的时候,可以采用二分查找

def binary_search(a_list, item):
    first = 0
    last = len(a_list) - 1
    found = False
    while first <= last and not found:
        midpoint = (first + last) // 2
        if a_list[midpoint] == item:
            found = True
        else:
            if item < a_list[midpoint]:
                last = midpoint - 1
            else:
                first = midpoint + 1
    return found

test_list = [0, 1, 2, 8, 13, 17, 19, 32, 42,]
print(binary_search(test_list, 3))
print(binary_search(test_list, 13))

(3) Hash查找:O(1),当序列中的元素是以某种特定的规律存放的时候,可以采用Hash查找

概念:hash,hash table,hash function 哈希表_on_wiki
image

image

三种查找方式都比较简单,本文剩下的内容侧重说下Hash查找相关的重要知识点

2.常用的哈希函数
(1) reminder method:取余数(size=11,下图对11取余数,例如17取余数得到6)
image

image

(2) folding method: 分组求和再取余数
image

image

(3) mid-square method:平方值的中间两位数取余数
image

image

(4) 对于由字符的元素可以尝试使用ord函数来将字符串转换成一个有序的数值序列:在Python中ord函数可以得到对应字符的ASCII码值,将所有字符的码值累加再取余数。
image

image

但是,对于通过回文构词法构成的字符串它们得到的值总是一样,为了解决这个问题,可以根据字符的位置添加一个权重。
image

image

From wiki
image

image

使用哈希查找,难免遇到冲突,那么冲突(Collision Resolution)该如何解决呢?

3.常用的解决冲突的办法
(1) open address(开放寻址):线性探测(linear probing)下一个位置,缺点是容易造成聚集现象(cluster),解决聚集现象的办法是跳跃式地查找下一个空槽。数值的顺序:(54, 26, 93, 17, 77, 31, 44, 55, 20).
image

image

(2) quadratic probing(平方探测):一开始的hash值为h,如果不是空槽,那就尝试h+1,还不是空槽就尝试h+4,依次继续尝试h+9,h+16等等。
image

image

(3) chain:利用链表链接起来
image

image

From wiki
image

image

4.分析hash查找的性能
一般使用平均查找长度来衡量,它的大小和装载因子有关**

散列表的载荷因子定义为:a = 填入表中的元素个数 / 散列表的长度

top Created with Sketch.