一、基本概念

查找（Searching）就是根據(jù)給定的某個(gè)值，在查找表中確定一個(gè)其關(guān)鍵字等于給定值的數(shù)據(jù)元素（或記錄）。

查找表（Search Table）：由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合

關(guān)鍵字（Key）：數(shù)據(jù)元素中某個(gè)數(shù)據(jù)項(xiàng)的值，又稱為鍵值。

主鍵（Primary Key）：可唯一地標(biāo)識(shí)某個(gè)數(shù)據(jù)元素或記錄的關(guān)鍵字。

查找表按照操作方式可分為：

• 靜態(tài)查找表（Static Search Table）：只做查找操作的查找表。它的主要操作是：
• 查詢某個(gè)“特定的”數(shù)據(jù)元素是否在表中
• 檢索某個(gè)“特定的”數(shù)據(jù)元素和各種屬性
• 動(dòng)態(tài)查找表（Dynamic Search Table）：在查找中同時(shí)進(jìn)行插入或刪除等操作：
• 查找時(shí)插入數(shù)據(jù)
• 查找時(shí)刪除數(shù)據(jù)

二、無序表查找

也就是數(shù)據(jù)不排序的線性查找，遍歷數(shù)據(jù)元素。

算法分析：最好情況是在第一個(gè)位置就找到了，此為O(1)；最壞情況在最后一個(gè)位置才找到，此為O(n)；所以平均查找次數(shù)為(n+1)/2。最終時(shí)間復(fù)雜度為O(n)

# 最基礎(chǔ)的遍歷無序列表的查找算法
# 時(shí)間復(fù)雜度O(n)

def sequential_search(lis, key):
  length = len(lis)
  for i in range(length):
    if lis[i] == key:
      return i
    else:
      return False


if __name__ == '__main__':
  LIST = [1, 5, 8, 123, 22, 54, 7, 99, 300, 222]
  result = sequential_search(LIST, 123)
  print(result)

三、有序表查找

查找表中的數(shù)據(jù)必須按某個(gè)主鍵進(jìn)行某種排序！

1. 二分查找(Binary Search)

算法核心：在查找表中不斷取中間元素與查找值進(jìn)行比較，以二分之一的倍率進(jìn)行表范圍的縮小。

# 針對(duì)有序查找表的二分查找算法
# 時(shí)間復(fù)雜度O(log(n))

def binary_search(lis, key):
  low = 0
  high = len(lis) - 1
  time = 0
  while low < high:
    time += 1
    mid = int((low + high) / 2)
    if key < lis[mid]:
      high = mid - 1
    elif key > lis[mid]:
      low = mid + 1
    else:
      # 打印折半的次數(shù)
      print("times: %s" % time)
      return mid
  print("times: %s" % time)
  return False

if __name__ == '__main__':
  LIST = [1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444]
  result = binary_search(LIST, 99)
  print(result)

2. 插值查找

二分查找法雖然已經(jīng)很不錯(cuò)了，但還有可以優(yōu)化的地方。

有的時(shí)候，對(duì)半過濾還不夠狠，要是每次都排除十分之九的數(shù)據(jù)豈不是更好？選擇這個(gè)值就是關(guān)鍵問題，插值的意義就是：以更快的速度進(jìn)行縮減。

插值的核心就是使用公式：

value = (key - list[low])/(list[high] - list[low])

用這個(gè)value來代替二分查找中的1/2。

上面的代碼可以直接使用，只需要改一句。

# 插值查找算法
# 時(shí)間復(fù)雜度O(log(n))

def binary_search(lis, key):
  low = 0
  high = len(lis) - 1
  time = 0
  while low < high:
    time += 1
    # 計(jì)算mid值是插值算法的核心代碼
    mid = low + int((high - low) * (key - lis[low])/(lis[high] - lis[low]))
    print("mid=%s, low=%s, high=%s" % (mid, low, high))
    if key < lis[mid]:
      high = mid - 1
    elif key > lis[mid]:
      low = mid + 1
    else:
      # 打印查找的次數(shù)
      print("times: %s" % time)
      return mid
  print("times: %s" % time)
  return False

if __name__ == '__main__':
  LIST = [1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444]
  result = binary_search(LIST, 444)
  print(result)

插值算法的總體時(shí)間復(fù)雜度仍然屬于O(log(n))級(jí)別的。其優(yōu)點(diǎn)是，對(duì)于表內(nèi)數(shù)據(jù)量較大，且關(guān)鍵字分布比較均勻的查找表，使用插值算法的平均性能比二分查找要好得多。反之，對(duì)于分布極端不均勻的數(shù)據(jù)，則不適合使用插值算法。

3. 斐波那契查找

由插值算法帶來的啟發(fā)，發(fā)明了斐波那契算法。其核心也是如何優(yōu)化那個(gè)縮減速率，使得查找次數(shù)盡量降低。

使用這種算法，前提是已經(jīng)有一個(gè)包含斐波那契數(shù)據(jù)的列表

F = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,...]

# 斐波那契查找算法
# 時(shí)間復(fù)雜度O(log(n))

def fibonacci_search(lis, key):
  # 需要一個(gè)現(xiàn)成的斐波那契列表。其最大元素的值必須超過查找表中元素個(gè)數(shù)的數(shù)值。
  F = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,
     233, 377, 610, 987, 1597, 2584, 4181, 6765,
     10946, 17711, 28657, 46368]
  low = 0
  high = len(lis) - 1
  
  # 為了使得查找表滿足斐波那契特性，在表的最后添加幾個(gè)同樣的值
  # 這個(gè)值是原查找表的最后那個(gè)元素的值
  # 添加的個(gè)數(shù)由F[k]-1-high決定
  k = 0
  while high > F[k]-1:
    k += 1
  print(k)
  i = high
  while F[k]-1 > i:
    lis.append(lis[high])
    i += 1
  print(lis)
  
  # 算法主邏輯。time用于展示循環(huán)的次數(shù)。
  time = 0
  while low <= high:
    time += 1
    # 為了防止F列表下標(biāo)溢出，設(shè)置if和else
    if k < 2:
      mid = low
    else:
      mid = low + F[k-1]-1
    
    print("low=%s, mid=%s, high=%s" % (low, mid, high))
    if key < lis[mid]:
      high = mid - 1
      k -= 1
    elif key > lis[mid]:
      low = mid + 1
      k -= 2
    else:
      if mid <= high:
        # 打印查找的次數(shù)
        print("times: %s" % time)
        return mid
      else:
        print("times: %s" % time)
        return high
  print("times: %s" % time)
  return False

if __name__ == '__main__':
  LIST = [1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444]
  result = fibonacci_search(LIST, 444)
  print(result)

算法分析：斐波那契查找的整體時(shí)間復(fù)雜度也為O(log(n))。但就平均性能，要優(yōu)于二分查找。但是在最壞情況下，比如這里如果key為1，則始終處于左側(cè)半?yún)^(qū)查找，此時(shí)其效率要低于二分查找。

總結(jié)：二分查找的mid運(yùn)算是加法與除法，插值查找則是復(fù)雜的四則運(yùn)算，而斐波那契查找只是最簡(jiǎn)單的加減運(yùn)算。在海量數(shù)據(jù)的查找中，這種細(xì)微的差別可能會(huì)影響最終的查找效率。因此，三種有序表的查找方法本質(zhì)上是分割點(diǎn)的選擇不同，各有優(yōu)劣，應(yīng)根據(jù)實(shí)際情況進(jìn)行選擇。

四、線性索引查找

對(duì)于海量的無序數(shù)據(jù)，為了提高查找速度，一般會(huì)為其構(gòu)造索引表。

索引就是把一個(gè)關(guān)鍵字與它相對(duì)應(yīng)的記錄進(jìn)行關(guān)聯(lián)的過程。

一個(gè)索引由若干個(gè)索引項(xiàng)構(gòu)成，每個(gè)索引項(xiàng)至少包含關(guān)鍵字和其對(duì)應(yīng)的記錄在存儲(chǔ)器中的位置等信息。

索引按照結(jié)構(gòu)可以分為：線性索引、樹形索引和多級(jí)索引。

線性索引：將索引項(xiàng)的集合通過線性結(jié)構(gòu)來組織，也叫索引表。

線性索引可分為：稠密索引、分塊索引和倒排索引

1.稠密索引

稠密索引指的是在線性索引中，為數(shù)據(jù)集合中的每個(gè)記錄都建立一個(gè)索引項(xiàng)。

這其實(shí)就相當(dāng)于給無序的集合，建立了一張有序的線性表。其索引項(xiàng)一定是按照關(guān)鍵碼進(jìn)行有序的排列。

這也相當(dāng)于把查找過程中需要的排序工作給提前做了。

1.分塊索引

給大量的無序數(shù)據(jù)集合進(jìn)行分塊處理，使得塊內(nèi)無序，塊與塊之間有序。

這其實(shí)是有序查找和無序查找的一種中間狀態(tài)或者說妥協(xié)狀態(tài)。因?yàn)閿?shù)據(jù)量過大，建立完整的稠密索引耗時(shí)耗力，占用資源過多；但如果不做任何排序或者索引，那么遍歷的查找也無法接受，只能折中，做一定程度的排序或索引。

分塊索引的效率比遍歷查找的O(n)要高一些，但與二分查找的O(logn)還是要差不少。

1.倒排索引

不是由記錄來確定屬性值，而是由屬性值來確定記錄的位置，這種被稱為倒排索引。其中記錄號(hào)表存儲(chǔ)具有相同次關(guān)鍵字的所有記錄的地址或引用（可以是指向記錄的指針或該記錄的主關(guān)鍵字）。

倒排索引是最基礎(chǔ)的搜索引擎索引技術(shù)。

五、二叉排序樹

二叉排序樹又稱為二叉查找樹。它或者是一顆空樹，或者是具有下列性質(zhì)的二叉樹：

• 若它的左子樹不為空，則左子樹上所有節(jié)點(diǎn)的值均小于它的根結(jié)構(gòu)的值；
• 若它的右子樹不為空，則右子樹上所有節(jié)點(diǎn)的值均大于它的根結(jié)構(gòu)的值；
• 它的左、右子樹也分別為二叉排序樹。

構(gòu)造一顆二叉排序樹的目的，往往不是為了排序，而是為了提高查找和插入刪除關(guān)鍵字的速度。

二叉排序樹的操作：

1.查找：對(duì)比節(jié)點(diǎn)的值和關(guān)鍵字，相等則表明找到了；小了則往節(jié)點(diǎn)的左子樹去找，大了則往右子樹去找，這么遞歸下去，最后返回布爾值或找到的節(jié)點(diǎn)。

2.插入：從根節(jié)點(diǎn)開始逐個(gè)與關(guān)鍵字進(jìn)行對(duì)比，小了去左邊，大了去右邊，碰到子樹為空的情況就將新的節(jié)點(diǎn)鏈接。

3.刪除：如果要?jiǎng)h除的節(jié)點(diǎn)是葉子，直接刪；如果只有左子樹或只有右子樹，則刪除節(jié)點(diǎn)后，將子樹鏈接到父節(jié)點(diǎn)即可；如果同時(shí)有左右子樹，則可以將二叉排序樹進(jìn)行中序遍歷，取將要被刪除的節(jié)點(diǎn)的前驅(qū)或者后繼節(jié)點(diǎn)替代這個(gè)被刪除的節(jié)點(diǎn)的位置。

#!/usr/bin/env python
# -*- coding:utf-8 -*-
# Author: Liu Jiang
# Python 3.5


class BSTNode:
  """
  定義一個(gè)二叉樹節(jié)點(diǎn)類。
  以討論算法為主，忽略了一些諸如對(duì)數(shù)據(jù)類型進(jìn)行判斷的問題。
  """
  def __init__(self, data, left=None, right=None):
    """
    初始化
    :param data: 節(jié)點(diǎn)儲(chǔ)存的數(shù)據(jù)
    :param left: 節(jié)點(diǎn)左子樹
    :param right: 節(jié)點(diǎn)右子樹
    """
    self.data = data
    self.left = left
    self.right = right


class BinarySortTree:
  """
  基于BSTNode類的二叉排序樹。維護(hù)一個(gè)根節(jié)點(diǎn)的指針。
  """
  def __init__(self):
    self._root = None

  def is_empty(self):
    return self._root is None

  def search(self, key):
    """
    關(guān)鍵碼檢索
    :param key: 關(guān)鍵碼
    :return: 查詢節(jié)點(diǎn)或None
    """
    bt = self._root
    while bt:
      entry = bt.data
      if key < entry:
        bt = bt.left
      elif key > entry:
        bt = bt.right
      else:
        return entry
    return None

  def insert(self, key):
    """
    插入操作
    :param key:關(guān)鍵碼 
    :return: 布爾值
    """
    bt = self._root
    if not bt:
      self._root = BSTNode(key)
      return
    while True:
      entry = bt.data
      if key < entry:
        if bt.left is None:
          bt.left = BSTNode(key)
          return
        bt = bt.left
      elif key > entry:
        if bt.right is None:
          bt.right = BSTNode(key)
          return
        bt = bt.right
      else:
        bt.data = key
        return

  def delete(self, key):
    """
    二叉排序樹最復(fù)雜的方法
    :param key: 關(guān)鍵碼
    :return: 布爾值
    """
    p, q = None, self._root   # 維持p為q的父節(jié)點(diǎn)，用于后面的鏈接操作
    if not q:
      print("空樹！")
      return
    while q and q.data != key:
      p = q
      if key < q.data:
        q = q.left
      else:
        q = q.right
      if not q:        # 當(dāng)樹中沒有關(guān)鍵碼key時(shí)，結(jié)束退出。
        return
    # 上面已將找到了要?jiǎng)h除的節(jié)點(diǎn)，用q引用。而p則是q的父節(jié)點(diǎn)或者None（q為根節(jié)點(diǎn)時(shí)）。
    if not q.left:
      if p is None:
        self._root = q.right
      elif q is p.left:
        p.left = q.right
      else:
        p.right = q.right
      return
    # 查找節(jié)點(diǎn)q的左子樹的最右節(jié)點(diǎn)，將q的右子樹鏈接為該節(jié)點(diǎn)的右子樹
    # 該方法可能會(huì)增大樹的深度，效率并不算高?？梢栽O(shè)計(jì)其它的方法。
    r = q.left
    while r.right:
      r = r.right
    r.right = q.right
    if p is None:
      self._root = q.left
    elif p.left is q:
      p.left = q.left
    else:
      p.right = q.left

  def __iter__(self):
    """
    實(shí)現(xiàn)二叉樹的中序遍歷算法,
    展示我們創(chuàng)建的二叉排序樹.
    直接使用python內(nèi)置的列表作為一個(gè)棧。
    :return: data
    """
    stack = []
    node = self._root
    while node or stack:
      while node:
        stack.append(node)
        node = node.left
      node = stack.pop()
      yield node.data
      node = node.right


if __name__ == '__main__':
  lis = [62, 58, 88, 48, 73, 99, 35, 51, 93, 29, 37, 49, 56, 36, 50]
  bs_tree = BinarySortTree()
  for i in range(len(lis)):
    bs_tree.insert(lis[i])
  # bs_tree.insert(100)
  bs_tree.delete(58)
  for i in bs_tree:
    print(i, end=" ")
  # print("\n", bs_tree.search(4))

二叉排序樹總結(jié)：

• 二叉排序樹以鏈?zhǔn)竭M(jìn)行存儲(chǔ)，保持了鏈接結(jié)構(gòu)在插入和刪除操作上的優(yōu)點(diǎn)。
• 在極端情況下，查詢次數(shù)為1，但最大操作次數(shù)不會(huì)超過樹的深度。也就是說，二叉排序樹的查找性能取決于二叉排序樹的形狀，也就引申出了后面的平衡二叉樹。
• 給定一個(gè)元素集合，可以構(gòu)造不同的二叉排序樹，當(dāng)它同時(shí)是一個(gè)完全二叉樹的時(shí)候，查找的時(shí)間復(fù)雜度為O(log(n))，近似于二分查找。
• 當(dāng)出現(xiàn)最極端的斜樹時(shí)，其時(shí)間復(fù)雜度為O(n)，等同于順序查找，效果最差。

六、 平衡二叉樹

平衡二叉樹（AVL樹，發(fā)明者的姓名縮寫）：一種高度平衡的排序二叉樹，其每一個(gè)節(jié)點(diǎn)的左子樹和右子樹的高度差最多等于1。

平衡二叉樹首先必須是一棵二叉排序樹！

平衡因子（Balance Factor）：將二叉樹上節(jié)點(diǎn)的左子樹深度減去右子樹深度的值。

對(duì)于平衡二叉樹所有包括分支節(jié)點(diǎn)和葉節(jié)點(diǎn)的平衡因子只可能是-1,0和1，只要有一個(gè)節(jié)點(diǎn)的因子不在這三個(gè)值之內(nèi)，該二叉樹就是不平衡的。

最小不平衡子樹：距離插入結(jié)點(diǎn)最近的，且平衡因子的絕對(duì)值大于1的節(jié)點(diǎn)為根的子樹。

平衡二叉樹的構(gòu)建思想：每當(dāng)插入一個(gè)新結(jié)點(diǎn)時(shí)，先檢查是否破壞了樹的平衡性，若有，找出最小不平衡子樹。在保持二叉排序樹特性的前提下，調(diào)整最小不平衡子樹中各結(jié)點(diǎn)之間的連接關(guān)系，進(jìn)行相應(yīng)的旋轉(zhuǎn)，成為新的平衡子樹。

下面是由[1,2,3,4,5,6,7,10,9]構(gòu)建平衡二叉樹

七、多路查找樹（B樹）

多路查找樹（muitl-way search tree）：其每一個(gè)節(jié)點(diǎn)的孩子可以多于兩個(gè)，且每一個(gè)結(jié)點(diǎn)處可以存儲(chǔ)多個(gè)元素。
 對(duì)于多路查找樹，每個(gè)節(jié)點(diǎn)可以存儲(chǔ)多少個(gè)元素，以及它的孩子數(shù)的多少是關(guān)鍵，常用的有這4種形式：2-3樹、2-3-4樹、B樹和B+樹。

2-3樹

2-3樹：每個(gè)結(jié)點(diǎn)都具有2個(gè)孩子，或者3個(gè)孩子，或者沒有孩子。

一個(gè)2結(jié)點(diǎn)包含一個(gè)元素和兩個(gè)孩子（或者沒有孩子，不能只有一個(gè)孩子）。與二叉排序樹類似，其左子樹包含的元素都小于該元素，右子樹包含的元素都大于該元素。

一個(gè)3結(jié)點(diǎn)包含兩個(gè)元素和三個(gè)孩子（或者沒有孩子，不能只有一個(gè)或兩個(gè)孩子）。

2-3樹中所有的葉子都必須在同一層次上。

其插入操作如下：

 其刪除操作如下：

2-3-4樹

其實(shí)就是2-3樹的擴(kuò)展，包括了4結(jié)點(diǎn)的使用。一個(gè)4結(jié)點(diǎn)包含小中大三個(gè)元素和四個(gè)孩子（或沒有孩子）。

其插入操作:

其刪除操作：

B樹

B樹是一種平衡的多路查找樹。節(jié)點(diǎn)最大的孩子數(shù)目稱為B樹的階（order）。2-3樹是3階B樹，2-3-4是4階B樹。

B樹的數(shù)據(jù)結(jié)構(gòu)主要用在內(nèi)存和外部存儲(chǔ)器的數(shù)據(jù)交互中。

B+樹

為了解決B樹的所有元素遍歷等基本問題，在原有的結(jié)構(gòu)基礎(chǔ)上，加入新的元素組織方式后，形成了B+樹。

B+樹是應(yīng)文件系統(tǒng)所需而出現(xiàn)的一種B樹的變形樹，嚴(yán)格意義上將，它已經(jīng)不是最基本的樹了。

B+樹中，出現(xiàn)在分支節(jié)點(diǎn)中的元素會(huì)被當(dāng)做他們?cè)谠摲种Ч?jié)點(diǎn)位置的中序后繼者（葉子節(jié)點(diǎn)）中再次列出。另外，每一個(gè)葉子節(jié)點(diǎn)都會(huì)保存一個(gè)指向后一葉子節(jié)點(diǎn)的指針。

所有的葉子節(jié)點(diǎn)包含全部的關(guān)鍵字的信息，及相關(guān)指針，葉子節(jié)點(diǎn)本身依關(guān)鍵字的大小自小到大順序鏈接

B+樹的結(jié)構(gòu)特別適合帶有范圍的查找。比如查找年齡在20~30歲之間的人。

八、散列表（哈希表）

散列表：所有的元素之間沒有任何關(guān)系。元素的存儲(chǔ)位置，是利用元素的關(guān)鍵字通過某個(gè)函數(shù)直接計(jì)算出來的。這個(gè)一一對(duì)應(yīng)的關(guān)系函數(shù)稱為散列函數(shù)或Hash函數(shù)。

采用散列技術(shù)將記錄存儲(chǔ)在一塊連續(xù)的存儲(chǔ)空間中，稱為散列表或哈希表（Hash Table）。關(guān)鍵字對(duì)應(yīng)的存儲(chǔ)位置，稱為散列地址。

散列表是一種面向查找的存儲(chǔ)結(jié)構(gòu)。它最適合求解的問題是查找與給定值相等的記錄。但是對(duì)于某個(gè)關(guān)鍵字能對(duì)應(yīng)很多記錄的情況就不適用，比如查找所有的“男”性。也不適合范圍查找，比如查找年齡20~30之間的人。排序、最大、最小等也不合適。

因此，散列表通常用于關(guān)鍵字不重復(fù)的數(shù)據(jù)結(jié)構(gòu)。比如python的字典數(shù)據(jù)類型。

設(shè)計(jì)出一個(gè)簡(jiǎn)單、均勻、存儲(chǔ)利用率高的散列函數(shù)是散列技術(shù)中最關(guān)鍵的問題。

 但是，一般散列函數(shù)都面臨著沖突的問題。

沖突：兩個(gè)不同的關(guān)鍵字，通過散列函數(shù)計(jì)算后結(jié)果卻相同的現(xiàn)象。collision。

8.1 散列函數(shù)的構(gòu)造方法

好的散列函數(shù)：計(jì)算簡(jiǎn)單、散列地址分布均勻

1.直接定址法

 例如取關(guān)鍵字的某個(gè)線性函數(shù)為散列函數(shù)：

f(key) = a*key + b (a,b為常數(shù)）

2.數(shù)字分析法

 抽取關(guān)鍵字里的數(shù)字，根據(jù)數(shù)字的特點(diǎn)進(jìn)行地址分配

3.平方取中法 

將關(guān)鍵字的數(shù)字求平方，再截取部分

4.折疊法

 將關(guān)鍵字的數(shù)字分割后分別計(jì)算，再合并計(jì)算，一種玩弄數(shù)字的手段。

5.除留余數(shù)法

 最為常見的方法之一。

 對(duì)于表長(zhǎng)為m的數(shù)據(jù)集合，散列公式為：

f(key) = key mod p (p<=m)

 mod：取模（求余數(shù)）

 該方法最關(guān)鍵的是p的選擇，而且數(shù)據(jù)量較大的時(shí)候，沖突是必然的。一般會(huì)選擇接近m的質(zhì)數(shù)。

6.隨機(jī)數(shù)法

 選擇一個(gè)隨機(jī)數(shù)，取關(guān)鍵字的隨機(jī)函數(shù)值為它的散列地址。

f(key) = random(key)

總結(jié)，實(shí)際情況下根據(jù)不同的數(shù)據(jù)特性采用不同的散列方法，考慮下面一些主要問題：

• 計(jì)算散列地址所需的時(shí)間
• 關(guān)鍵字的長(zhǎng)度
• 散列表的大小
• 關(guān)鍵字的分布情況
• 記錄查找的頻率

8.2 處理散列沖突

1、開放定址法

就是一旦發(fā)生沖突，就去尋找下一個(gè)空的散列地址，只要散列表足夠大，空的散列地址總能找到，并將記錄存入。

公式是：

這種簡(jiǎn)單的沖突解決辦法被稱為線性探測(cè)，無非就是自家的坑被占了，就逐個(gè)拜訪后面的坑，有空的就進(jìn)，也不管這個(gè)坑是不是后面有人預(yù)定了的。

 線性探測(cè)帶來的最大問題就是沖突的堆積，你把別人預(yù)定的坑占了，別人也就要像你一樣去找坑。

改進(jìn)的辦法有二次方探測(cè)法和隨機(jī)數(shù)探測(cè)法。

2、再散列函數(shù)法

發(fā)生沖突時(shí)就換一個(gè)散列函數(shù)計(jì)算，總會(huì)有一個(gè)可以把沖突解決掉，它能夠使得關(guān)鍵字不產(chǎn)生聚集，但相應(yīng)地增加了計(jì)算的時(shí)間。

3、鏈接地址法
 碰到?jīng)_突時(shí)，不更換地址，而是將所有關(guān)鍵字為同義詞的記錄存儲(chǔ)在一個(gè)鏈表里，在散列表中只存儲(chǔ)同義詞子表的頭指針，如下圖：

這樣的好處是，不怕沖突多；缺點(diǎn)是降低了散列結(jié)構(gòu)的隨機(jī)存儲(chǔ)性能。本質(zhì)是用單鏈表結(jié)構(gòu)輔助散列結(jié)構(gòu)的不足。

4、公共溢出區(qū)法

其實(shí)就是為所有的沖突，額外開辟一塊存儲(chǔ)空間。如果相對(duì)基本表而言，沖突的數(shù)據(jù)很少的時(shí)候，使用這種方法比較合適。

8.3 散列表查找實(shí)現(xiàn)

下面是一段簡(jiǎn)單的實(shí)現(xiàn)代碼：

#!/usr/bin/env python
# -*- coding:utf-8 -*-
# Author: Liu Jiang
# Python 3.5
# 忽略了對(duì)數(shù)據(jù)類型，元素溢出等問題的判斷。


class HashTable:
  def __init__(self, size):
    self.elem = [None for i in range(size)] # 使用list數(shù)據(jù)結(jié)構(gòu)作為哈希表元素保存方法
    self.count = size # 最大表長(zhǎng)

  def hash(self, key):
    return key % self.count # 散列函數(shù)采用除留余數(shù)法

  def insert_hash(self, key):
    """插入關(guān)鍵字到哈希表內(nèi)"""
    address = self.hash(key) # 求散列地址
    while self.elem[address]: # 當(dāng)前位置已經(jīng)有數(shù)據(jù)了，發(fā)生沖突。
      address = (address+1) % self.count # 線性探測(cè)下一地址是否可用
    self.elem[address] = key # 沒有沖突則直接保存。

  def search_hash(self, key):
    """查找關(guān)鍵字，返回布爾值"""
    star = address = self.hash(key)
    while self.elem[address] != key:
      address = (address + 1) % self.count
      if not self.elem[address] or address == star: # 說明沒找到或者循環(huán)到了開始的位置
        return False
    return True


if __name__ == '__main__':
  list_a = [12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34]
  hash_table = HashTable(12)
  for i in list_a:
    hash_table.insert_hash(i)

  for i in hash_table.elem:
    if i:
      print((i, hash_table.elem.index(i)), end=" ")
  print("\n")

  print(hash_table.search_hash(15))
  print(hash_table.search_hash(33))

8.4 散列表查找性能分析

如果沒發(fā)生沖突，則其查找時(shí)間復(fù)雜度為O(1)，屬于最極端的好了。

但是，現(xiàn)實(shí)中沖突可不可避免的，下面三個(gè)方面對(duì)查找性能影響較大：

• 散列函數(shù)是否均勻
• 處理沖突的辦法
• 散列表的裝填因子（表內(nèi)數(shù)據(jù)裝滿的程度）

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

最新評(píng)論