顺序查找

按照基本的顺序排序，简单地从一个项移动到另一个项，直到找到我们正在寻找的项或遍历完整个列表。

顺序查找

def  sequentialSearch(alist,item):
    pos = 0
    found = False


    while pos < len(alist)  and not found:
        if alist[pos] == item:
            found = True
        else:
            pos += 1

    return  found


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

查找性能情况：

顺序查找性能
假设项的列表按升序排列。如果我们正在寻找的项存在于列表中，它在 n 个位置中的概率依旧相同。我们仍然会有相同数量的比较来找到该项。然而，如果该项不存在，则有一些优点。
有序列表中查找

def orderedSequentialSearch(alist,item):
    pos = 0
    found = False
    stop = False

    while pos < len(alist) and not found and not stop:
        if alist[pos] == item:
            found = True
        else:
            if alist[pos] > item:
                stop = True
            else:
                pos += 1

    return  found

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

查找性能情况：

有序列表中的查找性能

二分查找

二分查找从中间项开始，而不是按顺序查找列表。 如果该项是我们正在寻找的项，我们就完成了查找。 如果它不是，我们可以使用列表的有序性质来消除剩余项的一半。重复这个过程，直到找到我们的查找项或者确定查找项不存在。
下图展示了该算法如何快速地找到54：

二分查找

def binarySearch(alist,item):
    first = 0
    last = len(alist) - 1
    found = False

    while first <= last and not found:
        midpoint = (first + last) // 2
        if alist[midpoint] == item:
            found = True
        else:
            if item < alist[midpoint]:
                last = midpoint -1
            else:
                first = midpoint +1

    return found


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

递归实现：

def binarySearchRec(alist,item):
    if len(alist) == 0:
        return  False
    else:
        midpoint = len(alist) // 2
        if alist[midpoint] == item:
            return True
        else:
            if item < alist[midpoint]:
                return binarySearchRec(alist[:midpoint],item)
            else:
                return binarySearchRec(alist[midpoint+1:], item)


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

二分查找性能
求解 i 得出 i=logn 。 最大比较数相对于列表中的项是对数的。 因此，二分查找是 O(logn)。
Python中的 slice 运算符实际上是 O(k)。这意味着使用 slice 的二分查找将不会在严格的对数时间执行。幸运的是，这可以通过传递列表连同开始和结束索引(第一种实现方式)来纠正。
即使二分查找通常比顺序查找更好，但重要的是要注意，对于小的 n 值，排序的额外成本可能不值得。事实上，我们应该经常考虑采取额外的分类工作是否使搜索获得好处。如果我们可以排序一次，然后查找多次，排序的成本就不那么重要。然而，对于大型列表，一次排序可能是非常昂贵，从一开始就执行顺序查找可能是最好的选择。

Hash 查找

哈希表是以一种容易找到它们的方式存储的项的集合。哈希表的每个位置，通常称为一个槽，可以容纳一个项，并且由从 0 开始的整数值命名。
例如，我们有一个名为 0 的槽，名为 1 的槽，名为 2 的槽，以上。最初，哈希表不包含项，因此每个槽都为空。我们可以通过使用列表来实现一个哈希表，每个元素初始化为None 。下图展示了大小 m = 11 的哈希表。换句话说，在表中有 m 个槽，命名为 0 到 10。

Hash查找
项和该项在散列表中所属的槽之间的映射被称为hash 函数。 hash 函数将接收集合中的任何项，并在槽名范围内（0和 m-1之间）返回一个整数。假设我们有整数项54,26,93,17,77 和 31的集合。我们的第一个 hash 函数，有时被称为余数法 ，只需要一个项并将其除以表大小，返回剩余部分作为其散列值（h(item) = item％11）。
Hash查找
一旦计算了哈希值，我们可以将每个项插入到指定位置的哈希表中，下图所示。注意，11 个插槽中的 6 个现在已被占用。这被称为负载因子，通常表示为 λ=项数/表大小, 在这个例子中，λ = 6/11 。
Hash查找
现在，当我们要搜索一个项时，我们只需使用哈希函数来计算项的槽名称，然后检查哈希表以查看它是否存在。该搜索操作是 O(1)，因为需要恒定的时间量来计算散列值，然后在该位置索引散列表。
只有每个项映射到哈希表中的唯一位置，这种技术才会起作用。 例如，如果项 44 是我们集合中的下一个项，则它的散列值为0（44％11 == 0）。 因为 77 的哈希值也是 0，我们会有一个问题。根据散列函数，两个或更多项将需要在同一槽中。这种现象被称为碰撞也可以被称为冲突。显然，冲突使散列技术产生了问题。

hash 函数

给定项的集合，将每个项映射到唯一槽的散列函数被称为完美散列函数。如果我们知道项和集合将永远不会改变，那么可以构造一个完美的散列函数。不幸的是，给定任意的项集合，没有系统的方法来构建完美的散列函数。幸运的是，我们不需要散列函数是完美的，仍然可以提高性能。
总是具有完美散列函数的一种方式是增加散列表的大小，使得可以容纳项范围中的每个可能值。这保证每个项将具有唯一的槽。虽然这对于小数目的项是实用的，但是当可能项的数目大时是不可行的。例如，如果项是九位数的社保号码，则此方法将需要大约十亿个槽。如果我们只想存储 25 名学生的数据，我们将浪费大量的内存。
我们的目标是创建一个散列函数，最大限度地减少冲突数，易于计算，并均匀分布在哈希表中的项。有很多常用的方法来扩展简单余数法。

分组求和法

将项划分为相等大小的块（最后一块可能不是相等大小）。然后将这些块加在一起以求出散列值。例如，如果我们的项是电话号码436-555-4601，我们将取出数字，并将它们分成2位数43,65,55,46,01。43 + 65 + 55 + 46 + 01，我们得到 210。我们假设哈希表有 11 个槽，那么我们需要除以 11 。在这种情况下，210％11 为 1，因此电话号码 436-555-4601 散列到槽1 。一些分组求和法会在求和之前每隔一个反转。对于上述示例，我们得到 43 + 56 + 55 + 64 + 01 = 219，其给出 219％11 = 10 。

平方取中法

首先对该项平方，然后提取一部分数字结果。例如，如果项是 44，我们将首先计算44^2 = 1,936。通过提取中间两个数字 93，我们得到5（93％11）。下图展示了余数法和中间平方法下的项。

余数法和平方取中法对比
我们还可以为基于字符的项（如字符串）创建哈希函数。 词 cat 可以被认为是 ascii 值的序列。

>>> ord('c')
99
>>> ord('a')
97
>>> ord('t')
116

我们可以获取这三个 ascii 值，将它们相加，并使用余数方法获取散列值:

def  hash(astring,tablesize):
    sum = 0
    for pos in range(len(astring)):
        sum += ord(astring[pos])
        
    return sum % tablesize

Hash查找

但是如果字符串中如果包含相同的字符，那么他们的散列值就会一样：

print(hash("cat",11))
print(hash("act",11))

为了弥补这一点，我们可以使用字符的位置作为权重，如可采用下面的加权形式：

Hash查找

冲突解决

当两个项散列到同一个槽时，我们必须有一个系统的方法将第二个项放在散列表中。这个过程称为冲突解决。如前所述，如果散列函数是完美的，冲突将永远不会发生。然而，由于这通常是不可能的，所以冲突解决成为散列非常重要的部分。
解决冲突的一种方法是查找散列表，尝试查找到另一个空槽以保存导致冲突的项。一个简单的方法是从原始哈希值位置开始，然后以顺序方式移动槽，直到遇到第一个空槽。注意，我们可能需要回到第一个槽（循环）以查找整个散列表。这种冲突解决过程被称为开放寻址，因为它试图在散列表中找到下一个空槽或地址。通过系统地依次访问每个槽，我们执行称为线性探测的开放寻址技术。
初始的哈希表为：

Hash查找
当我们尝试将 44 放入槽 0 时，发生冲突。在线性探测下，我们逐个顺序观察，直到找到位置。在这种情况下，我们找到槽 1。再次，55 应该在槽 0 中，但是必须放置在槽 2 中，因为它是下一个开放位置。值 20 散列到槽 9 。由于槽 9 已满，我们进行线性探测。我们访问槽10,0,1和 2，最后在位置 3 找到一个空槽。
Hash查找
一旦我们使用开放寻址和线性探测建立了哈希表，我们就必须使用相同的方法来搜索项。假设我们想查找项 93 。当我们计算哈希值时，我们得到 5 。查看槽 5 得到 93，返回 True。如果我们正在寻找 20， 现在哈希值为 9，而槽 9 当前项为 31 。我们不能简单地返回 False，因为我们知道可能存在冲突。我们现在被迫做一个顺序搜索，从位置 10 开始寻找，直到我们找到项 20 或我们找到一个空槽。
线性探测的缺点是聚集的趋势;项在表中聚集。这意味着如果在相同的散列值处发生很多冲突，则将通过线性探测来填充多个周边槽。这将影响正在插入的其他项，正如我们尝试添加上面的项 20 时看到的。必须跳过一组值为 0 的值，最终找到开放位置。
该聚集如下所示：
Hash查找
处理聚集的一种方式是扩展线性探测技术，使得不是顺序地查找下一个开放槽，而是跳过槽，从而更均匀地分布已经引起冲突的项。这将潜在地减少发生的聚集。下图展示了使用加3 探头进行碰撞识别时的项。 这意味着一旦发生碰撞，我们将查看第三个槽，直到找到一个空。
Hash查找
在冲突后寻找另一个槽的过程重新散列。使用简单的线性探测，rehash 函数是 newhashvalue = rehash(oldhashvalue)其中 rehash(pos)=(pos + 1)％sizeoftable。 加3rehash 可以定义为rehash(pos)=(pos + 3)％sizeoftable。一般来说，rehash(pos)=(pos + skip)％sizeoftable。重要的是要注意，“跳过”的大小必须使得表中的所有槽最终都被访问。否则，表的一部分将不被使用。为了确保这一点，通常建议表大小是素数。这是我们在示例中使用 11 的原因。
线性探测思想的一个变种称为二次探测。代替使用常量 “跳过” 值，我们使用rehash 函数，将散列值递增 1，3，5，7，9， 依此类推。这意味着如果第一哈希值是 h，则连续值是h + 1，h + 4，h + 9，h + 16，等等。换句话说，二次探测使用由连续完全正方形组成的跳跃。下图展示了使用此技术放置之后的示例值。
Hash查找
用于处理冲突问题的替代方法是允许每个槽保持对项的集合（或链）的引用。链接允许许多项存在于哈希表中的相同位置。当发生冲突时，项仍然放在散列表的正确槽中。随着越来越多的项哈希到相同的位置，搜索集合中的项的难度增加。下图展示了添加到使用链接解决冲突的散列表时的项。
Hash查找
当我们要搜索一个项时，我们使用散列函数来生成它应该在的槽。由于每个槽都有一个集合，我们使用一种搜索技术来查找该项是否存在。优点是，平均来说，每个槽中可能有更少的项，因此搜索可能更有效。

实现 map 抽象数据类型

map 抽象数据类型定义如下。该结构是键与值之间的关联的无序集合。map 中的键都是唯一的，因此键和值之间存在一对一的关系。操作如下。

操作	描述	返回值
Map()	创建一个新的 map	返回一个空的 map 集合
put(key，val)	向 map 中添加一个新的键值对，如果键已经在 map 中，那么用新值替换旧值	不返回任何内容
get(key)	给定一个键，返回存储在 map 中的值或 None	返回存储在 map 中的值或 None
del	使用 del map[key] 形式的语句从 map 中删除键值对	返回布尔值
len()	返回存储在 map 中的键值对的数量	返回一个整数
in	key in map 语句	返回布尔值

哈希表的初始大小已经被选择为 11。尽管这是任意的，但是重要的是，大小是质数，使得冲突解决算法可以尽可能高效。

class HashTable:
    def __init__(self):
        self.size = 11
        self.slots = [None] * self.size
        self.data = [None] * self.size

    def put(self,key,data):
        hashvalue = self.hashfunction(key,len(self.slots))

        if self.slots[hashvalue] == None:
            self.slots[hashvalue] = key
            self.data[hashvalue] = data
        else:
            if self.slots[hashvalue] == key:
                self.data[hashvalue] = data
            else:
                nextslot = self.rehash(hashvalue,len(self.slots))
                while self.slots[nextslot] != None and self.slots[nextslot] != key:
                    nextslot = self.rehash(nextslot, len(self.slots))

                if self.slots[nextslot] == None:
                    self.slots[nextslot] = key
                    self.data[nextslot] = data
                else:
                    self.data[nextslot] = data

    def hashfunction(self,key,size):
        return key % size

    def rehash(self,oldresh,size):
        return (oldresh+1) % size


    def get(self,key):
        startslot = self.hashfunction(key,len(self.slots))

        data = None
        stop = False
        found = False
        position = startslot

        while self.slots[position] != None and not found and not stop:
            if self.slots[position] == key:
                found = True
                data = self.data[position]
            else:
                position = self.rehash(position,len(self.slots))
                if position == startslot:
                    stop = True
        return  data

    def __getitem__(self,key):
        return self.get(key)

    def __setitem__(self,key,data):
        self.put(key,data)

测试：

H=HashTable()
H[54]="cat"
H[26]="dog"
H[93]="lion"
H[17]="tiger"
H[77]="bird"
H[31]="cow"
H[44]="goat"
H[55]="pig"
H[20]="chicken"
print(H.slots)
print(H.data)

接下来，我们将访问和修改哈希表中的一些项。注意:

print(H[20])
H[20] = 'duck'
print(H[20])

hash法分析

在最好的情况下，散列将提供 O(1)，恒定时间搜索。然而，由于冲突，比较的数量通常不是那么简单。
分析散列表的使用的最重要的信息是负载因子 λ。概念上，如果 λ 小，则碰撞的机会较低，这意味着项更可能在它们所属的槽中。如果 λ 大，意味着表正在填满，则存在越来越多的冲突。这意味着冲突解决更困难，需要更多的比较来找到一个空槽。使用链接，增加的碰撞意味着每个链上的项数量增加。