Basic concepts of search

1. lookup table

A collection of data elements (or records) of the same type

2. Two types of lookup tables

• Static lookup table: Only searches are performed, no records need to be inserted or deleted.
• Dynamic lookup table: In addition to lookup, it also supports inserting and deleting records, and maintains the corresponding lookup structure.

3. basic terminology

Keyword: The value of a data item in the record, which can be used to identify a record
Two types of keywords: Primary keywords and secondary keywords
Primary Keyword: Uniquely identifies the data element
Secondary keywords: Can represent several data elements

4. Find evaluation metrics for an algorithm

The average number of keyword comparisons during the search process is called the average search length (ASL).During analysis, it is necessary to distinguish between search success and search failure, and explain the probability of each record being searched.

5. How to find

Sequential search, binary search, block search, binary sorted tree search, balanced binary tree search, B-tree, B+ tree, hash search

method 1️⃣ sequential search

Application Scope:

A lookup table represented by a sequential list or a linear linked list has no requirements on whether the elements in the table are ordered.

1. Representation of sequence table

typedef int KeyType;

typedef struct {
  KeyType key; // 记录的关键字
} ElemType;

typedef struct {
  ElemType *R; // R[0] 为哨兵，R[1] 到 R[length] 为实际记录
  int length; // 实际记录数，不包含哨兵
} SSTable;

2. Find the record with key as key in sequence table ST

Store the keyword key to be searched in the reserved header position R[0] ("Sentinel"), and compare it one by one from back to front, which eliminates the need to check whether the subscript is out of bounds during each comparison.The R array needs to be allocated length+1 elements; returning 0 indicates that the search failed, otherwise the actual recorded position is returned.

int Search_Seq(SSTable ST, KeyType key) {
  int i;
  ST.R[0].key = key;
  for (i = ST.length; ST.R[i].key != key; --i) {
    // 哨兵保证循环最迟在 i=0 时结束
  }
  return i;
}

3. Performance analysis of sequential search

Space complexity: O(1), requiring only one sentinel position and a fixed number of auxiliary variables.

Time Complexity: O(1) at best, O(n) at average and worst.

Average search length: Assume that n records in the table have the same probability of being searched, and the number of successful comparisons is from 1 to n.

ASL成功 = (1+2+…+n)/n = (n+1)/2

When the search fails, all n records need to be checked.For the above sentinel implementation, if combined with R [ 0 ] The comparison of is also taken into account, then ASL失败 = n+1 。

4. Characteristics of sequential search algorithm

The algorithm is simple and can be used for sequential storage and chain storage.The above code uses a sequence list; the linked list needs to be traversed along the pointer and cannot be accessed directly by subscript.

The search efficiency is low when n is large

Improvement measures: When the corresponding order conditions are met, binary search or block search can be used.

Method2️⃣:binary search

The prerequisites for half search are: The lookup table is ordered by keyword and supports random access.The following is an example of a sequence table arranged in ascending order.

1. thoughts

Binary Search compares the keyword key to be searched with the middle element of the current search interval.If they are equal, the search is successful; if the key is smaller, the search continues in the left half; if the key is larger, the search continues in the right half.Repeat this process until the target is found or the search interval is empty.

2. Example process

Find K=120 in the figure and compare it with 68, 100, 115, and 125 in sequence. Finally, high < low means the search fails.The complete sequence should be 8, 17, 25, 44, 68, 77, 98, 100, 115, 125; the "10" in the initial row of the original picture should be "100". If there are missing items in the last frame, this complete sequence should prevail.

3. Performance analysis

The binary search process can be described with a binary tree: the middle element of the current interval is used as the root node, and the left and right subintervals construct subtrees in the same way respectively to obtain the decision tree of the binary search.

After each comparison, the interval to be checked is reduced to at most half of its original size.The best time complexity is O(1), and the worst time complexity is O(log₂ n).The extra space complexity of the non-recursive implementation is O(1), and the recursive implementation requires O(log₂ n) call stack space at worst.

4. Algorithm description

Half search (non-recursive algorithm)

function Search_Bin(ST, key) {
  // 找到时返回从 0 开始的数组下标，否则返回 -1
  let low = 0;
  let high = ST.length - 1;
  while (low <= high) {
    // 用差值计算中点，也便于迁移到使用固定宽度整数的语言
    const mid = low + Math.floor((high - low) / 2);
    if (key === ST[mid]) {
      return mid;
    } else if (key < ST[mid]) {
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return -1;
}
console.log(Search_Bin([1,2,3,4,5,6,7,8,9], 3)); // 2
const example = [8,17,25,44,68,77,98,100,115,125];
console.log(Search_Bin(example, 120)); // -1，与上图一致

Half search (recursive algorithm)

function Search_Bin(ST, key, low, high) {
  if (low > high) {
    return -1; // 查找不到时返回 -1
  }
  const mid = low + Math.floor((high - low) / 2);
  if (key === ST[mid]) {
    return mid;
  } else if (key < ST[mid]) {
    return Search_Bin(ST, key, low, mid - 1);
  } else {
    return Search_Bin(ST, key, mid + 1, high);
  }
}
const L = [1,2,3,4,5,6,7,8,9];
console.log(Search_Bin(L, 3, 0, L.length - 1)); // 2

Method3️⃣:blocked search

Divide the lookup table into several blocks, requiring that all keywords in the previous block are smaller than the keywords in the next block, but order within the blocks is not required, that is, "order between blocks, but disorder within the blocks."

The maximum key of each block forms an ordered index table, and the index item also needs to record the starting position and range of the corresponding block.

👉Block search process

1. Use a binary search on the index table to find the first block with the largest key not less than key; if such a block does not exist, the search fails.What is being searched for here is the candidate block, which does not require key to be equal to the largest key in the index.
2. A sequential search is performed within the candidate block. If the key is found, it succeeds, otherwise it fails.

Block search performance analysis

Time complexity: There are b blocks, each block has at most s records.Using a binary search on the index table and then searching sequentially within the block, the worst-case time complexity is O(log₂ b+s); if a sequential search is also used on the index table, it will be O(b+s).

Applies to: Records can be chunked by keyword range and maintain ordered indexes.If the index table uses half search, it needs to support random access; within the block, it can be traversed sequentially, and all records are not required to be in order.

Advantages and disadvantages of block search:

Advantages: There is no need to keep order within the block, which often reduces record movement during insertions and deletions.

Disadvantages: Requires additional index space.After insertion and deletion, it is still necessary to maintain the ordering between blocks, the range of blocks, and index information, and adjust the blocking if necessary.

Applicable situations: If the linear table needs to be searched quickly and frequently changes dynamically, block search can be used.

Method4️⃣:lookup in tree table

Tree lookup tables can be dynamically maintained as records are inserted and deleted.When performing a simple search, if the key is found, it will be successful, otherwise a failure will be returned; if a "find and insert" operation is performed, a new record can be inserted at the location where the search failed.

Method 1: Binary sorting tree search

Binary sorting tree search: The premise is that the lookup table is organized into a binary sorting tree.

Thoughts:

If the binary sort tree is empty, the search fails.Otherwise, compare the key with the keyword of the root node: success if they are equal; continue searching the left subtree if the key is smaller; continue searching the right subtree if the key is larger.This process is repeated until the target is found or an empty subtree is entered.

Characteristics of binary sorting tree:

Binary sorting tree is an empty tree, or a binary tree that satisfies the following properties:

1. If its left subtree is not empty, the values of all nodes on the left subtree are less than the value of the root node
2. If its right subtree is not empty, then the values of all nodes on the right subtree are greater than the value of the root node
3. The left and right subtrees themselves are each a binary sorting tree.

The process of generating a binary sorting tree:

For example, Given keyword sequence: 79, 62, 68, 90, 88, 89, 17, 5, 100, 120

The picture demonstrates the insertion process of the first 8 keywords, and finally stops at the state of inserting 5.As the insertion continues, 100 becomes the right child of 90, and 120 becomes the right child of 100. These two steps are not drawn in the figure.

Algorithmic Thought:

1. If the binary sorting tree is empty, the search fails and a null pointer is returned.

2. If the binary sort tree is not empty, compare key with the key of the root node T->data.key.

1. If key is equal to T->data.key, the search is successful and the root node address is returned.
2. If key is less than T->data.key, continue to search the left subtree.
3. If key is greater than T->data.key, continue to search the right subtree.

3. Performance Analysis of Binary Sorting Tree

Assume the tree height is h, and the search time complexity is O(h).When the tree is balanced, h is O(log₂ n); when it degenerates into a single chain, h is O(n).If a single search directly hits the root node, the best time complexity is O(1).Binary search on a binary sort tree and an ordered sequence table each have applicable scenarios, and we cannot simply assume that the former is necessarily slower.

4. Problems: When the insertion order is inappropriate, it may degenerate into a single-chain structure, making the worst search time O(n).

Method 2: Balanced Binary Tree

Here we discuss AVL trees, which are binary sorted trees that maintain balance through operations such as rotation.

1. thoughts

The search method of AVL tree is the same as that of binary sorting tree: compare the current node and key, enter the left subtree or right subtree according to the size, until the target is found or the empty subtree is entered.Balance maintenance occurs during insertion and deletion, and simple search does not require rotation.

2. Example process

Step 1: Maintain the balance of the binary sort tree when inserting records. Step 2: Search according to the binary sorting tree method.

Balanced binary tree definition:

If the absolute value of the difference between the heights of the left and right subtrees of each node in a binary sorted tree does not exceed 1, it is called an AVL tree.

Balance Factor:

Subtract the height of the right subtree from the height of the left subtree to obtain the balance factor of the node.

Description:

In a binary sorting tree, when the balance factors of all nodes can only be 0, 1, and -1, then the binary sorting tree is a balanced binary tree.

Step 1: Balancing of unbalanced binary trees

After inserting a node, the originally balanced binary sort tree may become unbalanced.Along the insertion path upward, find the ancestor node closest to the insertion point and with an absolute value of the balance factor greater than 1, and rotate it.The following describes four situations.

Case 1: LL type (left-left type), perform a right rotation on the unbalanced node.

Case 2: LR type (left-right type), first rotate the left child of the unbalanced node left, and then rotate the unbalanced node right.

Case 3: RR type (right-right type), perform a left rotation on the unbalanced node.

Case 4: RL type (right-left type), first rotate the right child of the unbalanced node right, and then rotate the unbalanced node left.

3. Search and performance analysis of balanced binary trees

AVL trees keep the tree height at O(log₂ n), so the worst-case search time complexity is O(log₂ n), which does not degenerate to O(n) like ordinary binary sort trees.When a single search directly hits the root node, the best time complexity is still O(1).

Method 3: B-tree

1. Definition: B-tree is a balanced multi-way search tree

This article refers to B-tree as B-tree for short, and order m means that a node has at most m subtrees.A B-tree of order m is either an empty tree or satisfies the following properties:

1. Each node has at most m-1 keywords; non-leaf nodes have at most m subtrees.
2. If the root node is not a leaf node, there are at least two subtrees.
3. Except for the root node, each non-leaf node has at least ⌈m/2⌉ subtrees, and each node has at least ⌈m/2⌉-1 keywords.⌈m/2⌉ means rounding up.
4. The keywords in the node are arranged in ascending order. A non-leaf node containing n keywords has n+1 subtrees, and the keywords of each subtree fall within the corresponding separation range.
5. Non-leaf nodes can be expressed as (n, A₀, K₁, A₁, …, Kₙ, Aₙ), where n is the number of keywords, K is the keyword, and A is the subtree pointer.
6. All leaf nodes are on the same level.

For example, the non-leaf nodes of a 4-order B-tree can have at most 4 subtree pointers, and each node can have at most 3 keywords.

The above restrictions on the minimum number of keywords and subtrees require the exclusion of the root node; the root node of a non-empty tree can have only one keyword, and the leaf nodes have no subtrees.

B-tree deletion: Brothers enough, low, high, low.If you don’t have enough brothers, pull them down and merge them.

This formula is used when there are insufficient keywords in the node after deletion: if the adjacent brother has excess keywords, adjust it with the help of the parent node; if the brother does not have excess keywords, move the separating keyword in the parent node down and merge it with the sibling node.If the parent node is insufficient because of this, it needs to continue to be adjusted upward.

After deleting keyword 53 in the figure, the leaf node becomes empty, and the right brother only has keyword 70, which cannot be lent.Therefore, 61 in the parent node is moved down and merged with the right sibling into a node containing 61 and 70, while the parent node retains 90.

Method 4: B+ tree

1. B+ tree is a variant of B-tree. The main differences between the two are as follows.

Convention adopted in this article: Each index item of a non-leaf node corresponds to a subtree, and the index key is the largest key of the subtree.Therefore, the number of keywords of non-leaf nodes is the same as the number of subtrees. A node of order m can have at most m index items; a leaf node can store at most m keywords.Different textbooks and implementations may also use the definition of separated keywords, and their node capacities and update rules need to be distinguished.

The leaf layer contains all keywords and pointers to corresponding records. Each leaf node is linked in order from small to large keywords, which facilitates sequential access and range search.

Non-leaf nodes only store index keys and subtree pointers, and the actual recorded information is located at the leaf layer.

Operation: B+ tree search, insertion, deletion

The process of searching, inserting, and deleting by given keywords on the B+ tree is similar to that of the B-tree, but ultimately the leaf node needs to be located.

Search: According to the convention of this article, each layer selects the first subtree with the largest keyword not less than key.Even if the key is equal to the index key in the non-leaf node, you still need to continue downward to confirm whether the record exists in the leaf node.If there is no candidate subtree, or the key does not exist in the leaf, the search fails.

The height and search performance analysis of B+ trees are similar to B-trees.When the order is fixed, the worst-case search time is O(log₂ n), and a larger number of branches can reduce the number of layers visited.

Insert: Records are inserted into leaf nodes.According to the agreement in this article, when the number of keywords exceeds m, it needs to be split into two nodes, retaining ⌊(m+1)/2⌋ and ⌈(m+1)/2⌉ keywords respectively, and maintaining the maximum keywords and pointers of these two nodes in the parent node.If the parent node also exceeds the capacity, it will continue to split upward; if the maximum key of the subtree changes, the upper index also needs to be updated.

Delete: The record is deleted from the leaf node.According to the maximum keyword index convention adopted in this article, if the maximum keyword of the subtree changes, the upper index needs to be updated simultaneously.If the number of keywords in a non-root node is less than ⌈m/2⌉, it will first try to borrow from sibling nodes, otherwise it will be merged and the parent node will continue to be maintained; the tree height will be reduced if necessary.

Method5️⃣:hash lookup

Advantages: Computing candidate storage locations through a hash function can usually reduce keyword comparisons; when a conflict occurs, the search still needs to be continued according to the corresponding rules.

1. Hash method: calculate storage location through function
2. Hash function: Function used in Hash method
3. Hash table: The table constructed according to the Hash method is called a Hash table
4. Hash address: Calculate the storage location of the record through the Hash function, called Hash address
5. Collision: Different keywords may get the same address after calculation by the Hash function, that is, key1 != key2, but H(key1) = H(key2).

Knowledge point 1. How to construct a Hash function?

Requirements: For a given key code set, choose a Hash function that is simple to calculate and has a relatively even address distribution to avoid or minimize conflicts.

Knowledge point 2. Formulate a plan to resolve conflicts

Requirements: Conflicts are allowed, but there must be a solution

Knowledge point 3. Performance of Hash search

Knowledge point 1: Construction of Hash function

When constructing a Hash function, you should pay attention to the following issues:

1. Time required to calculate Hash function
2. keyword length
3. Hash table size
4. Distribution of keywords
5. Record lookup frequency

1. direct addressing method

Take a linear function value of the keyword as the hash address.

Hash address:H(key) = a*key + b

Among them: a and b are fixed integers, and it is necessary to ensure that the calculated address is within the valid range of the table.

For integer keywords, when a is not 0 and the address range is sufficient, different keywords can be mapped to different addresses.This method is suitable for situations where the keyword range is small and the distribution is more continuous; when the keyword range is large and there are few records, storage space will be wasted.

2. division leaving remainder method

Assume the table length is m. For non-negative integer keywords, you can choose a positive integer p not larger than m. A common practice is to choose a prime number close to m, and then use the remainder as the address:

H(key) = key % p, where 0 < p <= m.The choice of p should be combined with the keyword distribution to avoid a large number of keywords getting the same remainder.

3. digital analytics

There are n d digits, each of which may have r different symbols.These r different symbols may not necessarily appear with the same frequency in each location.According to the size of the Hash table, several bits in which various symbols are evenly distributed can be selected as the Hash address.

4. Square-Medium Method

First square the keyword, and then take a few bits in the middle of the result as the hash address according to the size of the table.For example, by taking r binary bits, you can get an address in the range of 0 to 2ʳ-1; the address itself does not need to be a power of 2.

5. Folding method——There are two methods:

First type: The shift method aligns and adds the last bit of each part.

Second type: Boundary folding method folds back and forth along the boundaries of each part, which is equivalent to alternately reversing the order of numbers in adjacent parts, and then aligning and adding them.The addition result needs to be truncated or remaindered according to the size of the table to obtain the effective address.

6. random number method

The random number method uses a pseudo-random mapping with keywords as input, mapping the results to the valid address range of the table.

That is H(key) = random(key).

Random here represents a pseudo-random mapping with fixed parameters: the same keyword must get the same address in the same table.The random number generator cannot be called to generate a new address every time it is looked up.

Knowledge point 2: Develop a plan to resolve conflicts

Reason: Ideally, different keywords map to different addresses; in practice, multiple keywords may get the same address, which is called a collision. These keywords are called "synonyms" of each other.When a conflict occurs, existing records cannot be directly overwritten, and processing methods such as detection and linked lists need to be used.Whether there is a conflict depends on the hash function and the keyword set, and cannot be judged solely on whether the function is a linear function.

Collisions are usually difficult to completely avoid, and the performance of hash lookup is mainly related to the following three aspects.

The first is the packing factor α, which is the ratio of the number of elements n to the length of the table or number of buckets m: α = n/m.The open address method usually needs to keep α<1; the chain address method allows one bucket to store multiple records, so α can be greater than 1.Smaller α usually helps reduce probing or list traversal, but also increases free space, requiring a trade-off between time and space.

The second is related to the hash function constructed.

The third is related to conflict resolution methods.

The choice of loading factor depends on the conflict handling method and implementation, there is no universal "0.6~0.9 is optimal" range.

conflict resolution methods

1. open address law

The open address method stores records inside a hash table.The initial hash address is checked first, and other locations in the probing sequence are checked when a conflict occurs.

When inserting, it looks for available locations; when searching, it succeeds if it finds the target, and fails if it encounters an empty location that has never been used.There should be an upper limit on the number of probes to avoid infinite loops when the table is full or the probe sequence is repeated.When deleting records, you need to use methods such as deletion marks. You cannot directly change the position in the middle of the detection chain to an empty position that has never been used.

Described by the following formula:

Hᵢ(key) = (H(key) + dᵢ) % m, where i starts from 0 and d₀=0.

Where: Hᵢ(key) is the i-th candidate address, H(key) is the initial hash address, m is the table length, and dᵢ is the offset relative to the initial address.Some detection methods are prone to "clustering" phenomena, causing continuous conflicts to increase search overhead.

Generally, there are three values for address increment:

dᵢ = i, that is, 0, 1, 2, ..., m-1.

This situation is called linear detection and then hashing;

The offsets are 0, 1², -1², 2², -2², ..., K², -K², where K≤⌊m/2⌋.The address needs to be normalized to 0 to m-1 when calculating; in JavaScript, you can use ((H(key) + dᵢ) % m + m) % m.

In this case, it is secondary detection and then Hash:

The offset can also be generated by a pseudo-random sequence of fixed parameters, which is called pseudo-random detection and hash.Insertion and search of the same keyword must use the same detection sequence.

Secondary detection does not necessarily cover all locations. Even if there are still empty slots in the table, available locations may not be found; appropriate table length, filling factor, and expansion strategy are required.

2. chain address method

The chain address method links records with the same hash address in the linked list of the same bucket, and the headers of each bucket form an array.The length of the array is equal to the number of buckets m, which does not need to be the same as the number of keywords n.

3. Create a public overflow area

Establishing a public overflow area means storing these keywords in a separate public overflow area when a conflict occurs.The specific method is: assuming that the Hash address range is 0 to (m-1), let the vector HashTable[m] be the basic table, each component stores a record, and let a vector OverTable[n] be the overflow table.Store all records that conflict with keywords in the basic table into the overflow table.

4. Hash method

When a conflict occurs, the Hash method uses other hash functions to calculate candidate addresses, such as H₁(key), H₂(key), ..., Hₖ(key).Insertion and lookup require these functions in the same order.This approach can alleviate aggregation, but increases computational overhead and requires handling the case where none of the candidate locations are available.

Knowledge point 3: Hash search performance analysis (hash search performance analysis)

When the hash functions are distributed evenly, the fill factor is controlled, and the cost of keyword hashing and comparison is treated as a constant, the average hash lookup time is usually O(1).When there are a large number of conflicts, the worst-case time may reach O(n).The average search length depends on the conflict handling method, the loading factor, and whether the search is successful, and cannot be uniformly assumed to be 1.

1. Performance Analysis of Linear Exploration Method

Under the analysis assumptions that the initial hash addresses are independent and uniformly distributed, and that each record has an equal probability of successful search, when the table is large and α<1, the average number of detections for linear detection is approximately:

• Successfully found: ASL成功 ≈ 1/2 × [1 + 1/(1-α)]
• Failed to find: ASL失败 ≈ 1/2 × [1 + 1/(1-α)²]

As α approaches 1, the probing overhead increases significantly.The formula and analysis conditions can be found in Princeton University Hash Table Course Materials.

2. Performance analysis of zipper method search

The zipper method first locates the bucket and then compares the keywords along the linked list.When the hash addresses are independent, uniformly distributed and the probability of successful search of each record is equal:

• Successfully found: ASL成功 = 1 + (n-1)/(2m) ≈ 1 + α/2
• Failed to find: ASL失败 = α

Here ASL only counts the number of keyword comparisons in the linked list, and does not include the fixed overhead of calculating hash addresses and accessing buckets.