Detaillierte Erläuterung häufig verwendeter Suchdatenstrukturen und -algorithmen (Python-Implementierung)

1. Grundkonzepte

Bei der Suche geht es darum, ein Datenelement (oder einen Datensatz) zu ermitteln, dessen Schlüssel dem angegebenen Wert in der Nachschlagetabelle entspricht, basierend auf einem bestimmten Wert.

Suchtabelle: eine Sammlung von Datenelementen (oder Datensätzen) desselben Typs

Schlüssel: der Wert eines Datenelements im Datenelement, auch Schlüsselwert genannt.

Primärschlüssel: Ein Schlüsselwort, das ein Datenelement oder einen Datensatz eindeutig identifiziert.

Nachschlagetabellen können unterteilt werden in:

Statische Suchtabelle: eine Nachschlagetabelle, die nur Suchvorgänge ausführt. Seine Hauptoperationen sind:

Abfragen, ob ein „spezifisches“ Datenelement in der Tabelle vorhanden ist

Ein „spezifisches“ Datenelement und verschiedene Attribute abrufen

Dynamische Suchtabelle: Einfügen oder Löschvorgänge werden während der Suche gleichzeitig ausgeführt:

Daten während der Suche einfügen

Daten während der Suche löschen

2. Ungeordnete Tabellensuche

ist eine lineare Suche das Datenelemente durchläuft, ohne die Daten zu sortieren.

Algorithmusanalyse: Im besten Fall wird es an der ersten Position gefunden, also O(1); im schlechtesten Fall findet es sich an der letzten Position, also O(n). ); also Die durchschnittliche Anzahl der Suchvorgänge beträgt (n+1)/2. Die endgültige Zeitkomplexität ist O(n)

# 最基础的遍历无序列表的查找算法
# 时间复杂度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)

3. Geordnete Tabellensuche

Die Daten in der Nachschlagetabelle müssen nach einem Primärschlüssel sortiert werden!

1. Binäre Suche

Der Kern des Algorithmus: Vergleichen Sie kontinuierlich die Zwischenelemente in der Nachschlagetabelle mit dem Nachschlagewert und reduzieren Sie den Tabellenbereich auf die Hälfte.

# 针对有序查找表的二分查找算法
# 时间复杂度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:
      # 打印折半的次数
      print("times: %s" % time)
      return mid
  print("times: %s" % time)
  return False
 
if __name__ == &#39;__main__&#39;:
  LIST = [1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444]
  result = binary_search(LIST, 99)
  print(result)

2. Interpolationssuche

Obwohl die binäre Suchmethode bereits sehr gut ist, gibt es noch Bereiche, die optimiert werden können.

Manchmal ist die Halbierung nicht streng genug, wenn jedes Mal neun Zehntel der Daten ausgeschlossen würden. Die Wahl dieses Wertes ist das Schlüsselproblem. Die Bedeutung der Interpolation besteht darin, schneller zu reduzieren.

Der Kern der Interpolation besteht in der Verwendung der Formel:

Wert = (Schlüssel – Liste[niedrig])/(Liste[hoch] – Liste[niedrig])

Verwenden Sie diesen Wert, um 1/2 in der binären Suche zu ersetzen.

Der obige Code kann direkt verwendet werden, Sie müssen nur einen Satz ändern.

# 插值查找算法
# 时间复杂度O(log(n))
 
def binary_search(lis, key):
  low = 0
  high = len(lis) - 1
  time = 0
  while low < high:
    time += 1
    # 计算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:
      # 打印查找的次数
      print("times: %s" % time)
      return mid
  print("times: %s" % time)
  return False
 
if __name__ == &#39;__main__&#39;:
  LIST = [1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444]
  result = binary_search(LIST, 444)
  print(result)

Die Gesamtzeitkomplexität des Interpolationsalgorithmus liegt immer noch auf dem O(log(n))-Niveau. Der Vorteil besteht darin, dass bei Nachschlagetabellen mit einer großen Datenmenge in der Tabelle und einer relativ gleichmäßigen Verteilung der Schlüsselwörter die durchschnittliche Leistung der Verwendung des Interpolationsalgorithmus viel besser ist als bei der binären Suche. Im Gegenteil, für Daten mit extrem ungleichmäßiger Verteilung ist der Interpolationsalgorithmus nicht geeignet.

3. Fibonacci-Suche

Inspiriert durch den Interpolationsalgorithmus wurde der Fibonacci-Algorithmus erfunden. Im Kern geht es auch darum, die Reduktionsrate so zu optimieren, dass die Anzahl der Suchanfragen minimiert wird.

Verwenden Sie diesen Algorithmus, vorausgesetzt, es gibt bereits eine Liste mit Fibonacci-Daten

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

# 斐波那契查找算法
# 时间复杂度O(log(n))
 
def fibonacci_search(lis, key):
  # 需要一个现成的斐波那契列表。其最大元素的值必须超过查找表中元素个数的数值。
  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
   
  # 为了使得查找表满足斐波那契特性，在表的最后添加几个同样的值
  # 这个值是原查找表的最后那个元素的值
  # 添加的个数由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用于展示循环的次数。
  time = 0
  while low <= high:
    time += 1
    # 为了防止F列表下标溢出，设置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:
        # 打印查找的次数
        print("times: %s" % time)
        return mid
      else:
        print("times: %s" % time)
        return high
  print("times: %s" % time)
  return False
 
if __name__ == &#39;__main__&#39;:
  LIST = [1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444]
  result = fibonacci_search(LIST, 444)
  print(result)

Algorithmusanalyse: Die Gesamtzeitkomplexität der Fibonacci-Suche beträgt ebenfalls O(log (n)). Aber im Hinblick auf die durchschnittliche Leistung ist es besser als die binäre Suche. Aber im schlimmsten Fall, wenn der Schlüssel hier beispielsweise 1 ist, befindet sich die Suche immer im linken Halbbereich. Zu diesem Zeitpunkt ist ihre Effizienz geringer als bei der binären Suche.

Zusammenfassung: Die mittlere Operation der binären Suche ist Addition und Division, die Interpolationssuche besteht aus den vier komplexen arithmetischen Operationen und die Fibonacci-Suche ist nur die einfachste Additions- und Subtraktionsoperation. Bei der Suche nach großen Datenmengen kann sich dieser subtile Unterschied auf die endgültige Sucheffizienz auswirken. Daher unterscheiden sich die drei Suchmethoden für geordnete Tabellen bei der Auswahl der Teilungspunkte grundsätzlich. Jede hat ihre eigenen Vor- und Nachteile, und die Auswahl sollte auf der tatsächlichen Situation basieren.

4. Lineare Indexsuche

Um die Suchgeschwindigkeit zu verbessern, wird im Allgemeinen eine Indextabelle dafür erstellt.

Indizierung ist der Prozess der Verknüpfung eines Schlüsselworts mit dem entsprechenden Datensatz.

Ein Index besteht aus mehreren Indexelementen, und jedes Indexelement enthält mindestens Informationen wie Schlüsselwörter und die entsprechenden Speicherorte im Speicher.

Indizes können entsprechend ihrer Struktur in lineare Indizes, Baumindizes und mehrstufige Indizes unterteilt werden.

Linearer Index: Organisieren Sie die Sammlung von Indexelementen über eine lineare Struktur, auch Indextabelle genannt.

Linearer Index kann unterteilt werden in: dichten Index, Blockindex und invertierten Index

1. Dichter Index

Dichter Index bezieht sich auf Online In a Sexualindex wird für jeden Datensatz in der Datensammlung ein Indexeintrag erstellt.

Dies entspricht tatsächlich dem Erstellen einer geordneten linearen Liste für eine ungeordnete Menge. Die Indexelemente müssen entsprechend dem Schlüsselcode geordnet werden.

Dies ist auch gleichbedeutend damit, die im Suchprozess erforderlichen Sortierarbeiten vorab durchzuführen.

1. Der Blockindex

unterteilt eine große Anzahl ungeordneter Datensätze in Blöcke, sodass innerhalb des Blocks und zwischen den Blöcken eine Ordnung herrscht.

这其实是有序查找和无序查找的一种中间状态或者说妥协状态。因为数据量过大，建立完整的稠密索引耗时耗力，占用资源过多；但如果不做任何排序或者索引，那么遍历的查找也无法接受，只能折中，做一定程度的排序或索引。

分块索引的效率比遍历查找的O(n)要高一些，但与二分查找的O(logn)还是要差不少。

1.倒排索引

不是由记录来确定属性值，而是由属性值来确定记录的位置，这种被称为倒排索引。其中记录号表存储具有相同次关键字的所有记录的地址或引用（可以是指向记录的指针或该记录的主关键字）。

倒排索引是最基础的搜索引擎索引技术。

五、二叉排序树

二叉排序树又称为二叉查找树。它或者是一颗空树，或者是具有下列性质的二叉树：

若它的左子树不为空，则左子树上所有节点的值均小于它的根结构的值；

若它的右子树不为空，则右子树上所有节点的值均大于它的根结构的值；

它的左、右子树也分别为二叉排序树。

构造一颗二叉排序树的目的，往往不是为了排序，而是为了提高查找和插入删除关键字的速度。

二叉排序树的操作：

1.查找：对比节点的值和关键字，相等则表明找到了；小了则往节点的左子树去找，大了则往右子树去找，这么递归下去，最后返回布尔值或找到的节点。

2.插入：从根节点开始逐个与关键字进行对比，小了去左边，大了去右边，碰到子树为空的情况就将新的节点链接。

3.删除：如果要删除的节点是叶子，直接删；如果只有左子树或只有右子树，则删除节点后，将子树链接到父节点即可；如果同时有左右子树，则可以将二叉排序树进行中序遍历，取将要被删除的节点的前驱或者后继节点替代这个被删除的节点的位置。

#!/usr/bin/env python
# -*- coding:utf-8 -*-
# Author: Liu Jiang
# Python 3.5
 
 
class BSTNode:
  """
  定义一个二叉树节点类。
  以讨论算法为主，忽略了一些诸如对数据类型进行判断的问题。
  """
  def __init__(self, data, left=None, right=None):
    """
    初始化
    :param data: 节点储存的数据
    :param left: 节点左子树
    :param right: 节点右子树
    """
    self.data = data
    self.left = left
    self.right = right
 
 
class BinarySortTree:
  """
  基于BSTNode类的二叉排序树。维护一个根节点的指针。
  """
  def __init__(self):
    self._root = None
 
  def is_empty(self):
    return self._root is None
 
  def search(self, key):
    """
    关键码检索
    :param key: 关键码
    :return: 查询节点或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:关键码
    :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):
    """
    二叉排序树最复杂的方法
    :param key: 关键码
    :return: 布尔值
    """
    p, q = None, self._root   # 维持p为q的父节点，用于后面的链接操作
    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:        # 当树中没有关键码key时，结束退出。
        return
    # 上面已将找到了要删除的节点，用q引用。而p则是q的父节点或者None（q为根节点时）。
    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
    # 查找节点q的左子树的最右节点，将q的右子树链接为该节点的右子树
    # 该方法可能会增大树的深度，效率并不算高。可以设计其它的方法。
    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):
    """
    实现二叉树的中序遍历算法,
    展示我们创建的二叉排序树.
    直接使用python内置的列表作为一个栈。
    :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__ == &#39;__main__&#39;:
  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))

   

二叉排序树总结：

二叉排序树以链式进行存储，保持了链接结构在插入和删除操作上的优点。

在极端情况下，查询次数为1，但最大操作次数不会超过树的深度。也就是说，二叉排序树的查找性能取决于二叉排序树的形状，也就引申出了后面的平衡二叉树。

给定一个元素集合，可以构造不同的二叉排序树，当它同时是一个完全二叉树的时候，查找的时间复杂度为O(log(n))，近似于二分查找。

当出现最极端的斜树时，其时间复杂度为O(n)，等同于顺序查找，效果最差。

六、 平衡二叉树

平衡二叉树（AVL树，发明者的姓名缩写）：一种高度平衡的排序二叉树，其每一个节点的左子树和右子树的高度差最多等于1。

平衡二叉树首先必须是一棵二叉排序树！

平衡因子（Balance Factor）：将二叉树上节点的左子树深度减去右子树深度的值。

对于平衡二叉树所有包括分支节点和叶节点的平衡因子只可能是-1,0和1，只要有一个节点的因子不在这三个值之内，该二叉树就是不平衡的。

最小不平衡子树：距离插入结点最近的，且平衡因子的绝对值大于1的节点为根的子树。

平衡二叉树的构建思想：每当插入一个新结点时，先检查是否破坏了树的平衡性，若有，找出最小不平衡子树。在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的连接关系，进行相应的旋转，成为新的平衡子树。

下面是由[1,2,3,4,5,6,7,10,9]构建平衡二叉树

7. Mehrweg-Suchbaum (B-Baum)

Muitl-Weg-Suchbaum: die Kinder von jeder Knoten Es kann mehr als zwei geben und jeder Knoten kann mehrere Elemente speichern.
Bei mehrwegigen Suchbäumen kommt es darauf an, wie viele Elemente jeder Knoten speichern kann und wie viele untergeordnete Elemente es gibt. Es gibt vier häufig verwendete Formen: 2-3-Baum, 2-3-4-Baum und B-Baum. und B+-Bäume.

2-3-Baum

2-3-Baum: Jeder Knoten hat 2 Kinder, 3 Kinder oder keine Kinder.

Ein 2-Knoten enthält ein Element und zwei Kinder (oder keine Kinder, kann nicht nur ein Kind haben). Ähnlich wie bei einem binär sortierten Baum sind die im linken Teilbaum enthaltenen Elemente alle kleiner als das Element und die im rechten Teilbaum enthaltenen Elemente sind größer als das Element.

Ein 3-Knoten enthält zwei Elemente und drei Kinder (oder keine Kinder, nicht nur ein oder zwei Kinder).

2-3 Alle Blätter des Baumes müssen auf gleicher Höhe sein.

Der Einfügevorgang ist wie folgt:

Der Löschvorgang ist wie folgt:

2- 3-4-Baum

ist eigentlich eine Erweiterung des 2-3-Baums, einschließlich der Verwendung von 4 Knoten. Ein 4-Knoten enthält drei Elemente, klein, mittel und groß, und vier untergeordnete Elemente (oder keine untergeordneten Elemente).

Sein Einfügevorgang:

Sein Löschvorgang:

B-Baum

B-Tree ist ein ausgewogener Mehrweg-Suchbaum. Die maximale Anzahl von Kindern eines Knotens wird als Ordnung des B-Baums bezeichnet. Der 2-3-Baum ist ein B-Baum dritter Ordnung und der 2-3-4 ein B-Baum vierter Ordnung.

Die Datenstruktur von B-Tree wird hauptsächlich bei der Dateninteraktion zwischen Speicher und externem Speicher verwendet.

B+ Baum

Um die Durchquerung aller Elemente zu lösen des B-Baums usw. Das Grundproblem besteht darin, dass nach dem Hinzufügen einer neuen Elementorganisationsmethode zur ursprünglichen Struktur ein B+-Baum gebildet wird.

Der B+-Baum ist ein deformierter Baum des B-Baums, der als Reaktion auf die Anforderungen des Dateisystems erscheint. Streng genommen ist er nicht mehr der grundlegendste Baum.

In einem B+-Baum werden Elemente, die in einem Zweigknoten erscheinen, erneut als ihre Nachfolger in der Reihenfolge (Blattknoten) an dieser Zweigknotenposition aufgeführt. Darüber hinaus speichert jeder Blattknoten einen Zeiger auf den folgenden Blattknoten.

Alle Blattknoten enthalten Informationen zu allen Schlüsselwörtern und zugehörigen Zeigern. Die Blattknoten selbst sind entsprechend der Größe der Schlüsselwörter in aufsteigender Reihenfolge verknüpft.

Die Die Struktur des B+-Baums eignet sich besonders für Suchen mit Bereichen. Suchen Sie beispielsweise nach Personen im Alter zwischen 20 und 30 Jahren.

8. Hash-Tabelle (Hash-Tabelle)

Hash-Tabelle: Es besteht keine Beziehung zwischen allen Elementen. Der Speicherort des Elements wird direkt über eine Funktion berechnet, die das Schlüsselwort des Elements verwendet. Diese Eins-zu-Eins-Beziehungsfunktion wird als Hash-Funktion oder Hash-Funktion bezeichnet.

Hash-Technologie wird verwendet, um Datensätze in einem kontinuierlichen Speicherplatz zu speichern, der als Hash-Tabelle oder Hash-Tabelle (Hash-Tabelle) bezeichnet wird. Der dem Schlüsselwort entsprechende Speicherort wird Hash-Adresse genannt.

Hash-Tabelle ist eine suchorientierte Speicherstruktur. Das Problem, für das es am besten geeignet ist, besteht darin, Datensätze zu finden, die einem bestimmten Wert entsprechen. Es eignet sich jedoch nicht für Situationen, in denen ein bestimmtes Schlüsselwort vielen Datensätzen entsprechen kann, z. B. um alle „männlichen“ Geschlechter zu finden. Es ist auch nicht für Bereichssuchen geeignet, beispielsweise für die Suche nach Personen im Alter zwischen 20 und 30 Jahren. Sortierung, größte, kleinste usw. sind ebenfalls ungeeignet.

Daher werden Hash-Tabellen normalerweise für Datenstrukturen verwendet, bei denen Schlüsselwörter nicht wiederholt werden. Zum Beispiel der Wörterbuchdatentyp von Python.

Das Entwerfen einer einfachen, einheitlichen Hash-Funktion mit hoher Speicherauslastung ist das kritischste Problem in der Hashing-Technologie.

Bei allgemeinen Hash-Funktionen treten jedoch Konfliktprobleme auf.

Konflikt: Zwei verschiedene Schlüsselwörter haben nach der Berechnung durch die Hash-Funktion das gleiche Ergebnis. Kollision.

8.1 Konstruktionsmethode der Hash-Funktion

Gute Hash-Funktion: einfache Berechnung, gleichmäßige Hash-Adressverteilung

1. Direkte Adressierungsmethode

Nehmen Sie zum Beispiel eine lineare Funktion des Schlüssels als Hash-Funktion:

f(key) = a*key + b (a, b sind Konstanten)

2.数字分析法

 抽取关键字里的数字，根据数字的特点进行地址分配

3.平方取中法 

将关键字的数字求平方，再截取部分

4.折叠法

 将关键字的数字分割后分别计算，再合并计算，一种玩弄数字的手段。

5.除留余数法

 最为常见的方法之一。

 对于表长为m的数据集合，散列公式为：

f(key) = key mod p (p

 mod：取模（求余数）

 该方法最关键的是p的选择，而且数据量较大的时候，冲突是必然的。一般会选择接近m的质数。

6.随机数法

 选择一个随机数，取关键字的随机函数值为它的散列地址。

f(key) = random(key)

总结，实际情况下根据不同的数据特性采用不同的散列方法，考虑下面一些主要问题：

计算散列地址所需的时间

关键字的长度

散列表的大小

关键字的分布情况

记录查找的频率

8.2 处理散列冲突

1、开放定址法

就是一旦发生冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。

公式是：

这种简单的冲突解决办法被称为线性探测，无非就是自家的坑被占了，就逐个拜访后面的坑，有空的就进，也不管这个坑是不是后面有人预定了的。

 线性探测带来的最大问题就是冲突的堆积，你把别人预定的坑占了，别人也就要像你一样去找坑。

改进的办法有二次方探测法和随机数探测法。

2、再散列函数法

发生冲突时就换一个散列函数计算，总会有一个可以把冲突解决掉，它能够使得关键字不产生聚集，但相应地增加了计算的时间。

3、链接地址法
 碰到冲突时，不更换地址，而是将所有关键字为同义词的记录存储在一个链表里，在散列表中只存储同义词子表的头指针，如下图：

这样的好处是，不怕冲突多；缺点是降低了散列结构的随机存储性能。本质是用单链表结构辅助散列结构的不足。

4、公共溢出区法

其实就是为所有的冲突，额外开辟一块存储空间。如果相对基本表而言，冲突的数据很少的时候，使用这种方法比较合适。

8.3 散列表查找实现

下面是一段简单的实现代码：

#!/usr/bin/env python
# -*- coding:utf-8 -*-
# Author: Liu Jiang
# Python 3.5
# 忽略了对数据类型，元素溢出等问题的判断。
 
 
class HashTable:
  def __init__(self, size):
    self.elem = [None for i in range(size)] # 使用list数据结构作为哈希表元素保存方法
    self.count = size # 最大表长
 
  def hash(self, key):
    return key % self.count # 散列函数采用除留余数法
 
  def insert_hash(self, key):
    """插入关键字到哈希表内"""
    address = self.hash(key) # 求散列地址
    while self.elem[address]: # 当前位置已经有数据了，发生冲突。
      address = (address+1) % self.count # 线性探测下一地址是否可用
    self.elem[address] = key # 没有冲突则直接保存。
 
  def search_hash(self, key):
    """查找关键字，返回布尔值"""
    star = address = self.hash(key)
    while self.elem[address] != key:
      address = (address + 1) % self.count
      if not self.elem[address] or address == star: # 说明没找到或者循环到了开始的位置
        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 散列表查找性能分析

如果没发生冲突，则其查找时间复杂度为O(1)，属于最极端的好了。

但是，现实中冲突可不可避免的，下面三个方面对查找性能影响较大：

散列函数是否均匀

处理冲突的办法

散列表的装填因子（表内数据装满的程度）

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持PHP中文网。

更多Detaillierte Erläuterung häufig verwendeter Suchdatenstrukturen und -algorithmen (Python-Implementierung)相关文章请关注PHP中文网！