笙亿网络策划

DSA中Hashed Array Tree是什么？怎么实现哈希数组树数据结构？

约 27 分钟读完 0 阅
文章导读
Previous Quiz Next Hashed Array Tree 是一种用于以数组形式存储和管理数据的数据结构。它是数组和哈希表（hash table）的结合。Hashed Array Tree 结合了数组和哈希表的优点，例如快速访问元素和高效内存使用。
📋 目录
  1. 一 Hashed Array Tree 的工作原理
  2. 二 Hashed Array Tree 的操作
  3. 三 Hashed Array Tree 的实现
  4. 四 Hashed Array Tree 的时间复杂度
  5. 五 Hashed Array Tree 的应用
  6. 六 结论
A A

Hashed Array Tree

Previous
Quiz
Next

Hashed Array Tree 是一种用于以数组形式存储和管理数据的数据结构。它是数组和哈希表（hash table）的结合。Hashed Array Tree 结合了数组和哈希表的优点，例如快速访问元素和高效内存使用。

它具有动态大小，因此可以根据需要增长或缩小。Hashed Array Tree 使用一个存储元素的数组和一个将键映射到数组中元素索引的哈希表来实现。

Hashed Array Tree 的工作原理

让我们通过一个例子来理解 Hashed Array Tree 的工作原理：

假设我们有一组元素 {A, B, C, D, E, F, G, H, I, J}，我们希望将这些元素存储在 Hashed Array Tree 中。

Hashed Array Tree 的工作方式如下：

  • 初始时，我们创建一个大小为 'n' 的数组，以及一个将键映射到数组中元素索引的哈希表。
  • 对于集合中的每个元素，我们计算键的hash value，并将元素存储在数组中对应的索引位置。
  • 我们还将key 和index 存储在哈希表中。
  • 当我们想通过键访问元素时，我们计算键的hash value，并从哈希表中检索索引。
  • 然后，我们访问数组中检索到的索引处的元素。

Hashed Array Tree 的操作

Hashed Array Tree 支持以下操作：

  • Insert(key, value)： 将具有给定键和值的元素插入到 Hashed Array Tree 中。
  • Get(key)： 从 Hashed Array Tree 中检索具有给定键的元素。
  • Delete(key)： 从 Hashed Array Tree 中删除具有给定键的元素。

Hashed Array Tree 的实现

现在，让我们了解如何实现 hashed array tree。在实现 hashed array tree 时，我们需要注意几点：处理冲突、调整数组大小以及对键进行 rehashing。

插入操作的算法

以下是插入操作的算法 −

1.计算键的 hash 值。
2.检查 hash 值是否在数组边界内。
3.如果索引为空，则在该索引处插入元素。
4.如果索引不为空，则处理冲突。

插入操作的代码

以下是如何在 hashed array tree 中实现插入操作的示例：

C C++ Java Python 
// C 程序，用于在 Hashed Array Tree 上执行插入操作
#include <stdio.h>
#include <stdlib.h>

#define SIZE 10

int hashTable[SIZE] = {0};
int arr[SIZE] = {0};

int hashFunction(int key){
   return key % SIZE;
}

void insert(int key, int value){
   int index = hashFunction(key);
   while(arr[index] != 0){
      index = (index + 1) % SIZE;
   }
   arr[index] = value;
   hashTable[index] = key;
}

void display(){
   for(int i = 0; i < SIZE; i++){
      if(arr[i] != 0){
         printf("Key: %d, Value: %d\n", hashTable[i], arr[i]);
      }
   }
}

int main(){
   insert(3, 10);
   insert(13, 20);
   insert(23, 30);
   insert(33, 40);
   insert(43, 50);
   insert(53, 60);
   insert(63, 70);
   display();
   return 0;
}

输出

以下是上述 C 程序的输出：

Key: 3, Value: 10
Key: 13, Value: 20
Key: 23, Value: 30
Key: 33, Value: 40
Key: 43, Value: 50
Key: 53, Value: 60
Key: 63, Value: 70

// C++ 程序，用于在 Hashed Array Tree 上执行插入操作
#include <iostream>
using namespace std;

#define SIZE 10

int hashTable[SIZE] = {0};
int arr[SIZE] = {0};

int hashFunction(int key){
   return key % SIZE;
}

void insert(int key, int value){
   int index = hashFunction(key);
   while(arr[index] != 0){
      index = (index + 1) % SIZE;
   }
   arr[index] = value;
   hashTable[index] = key;
}

void display(){
   for(int i = 0; i < SIZE; i++){
      if(arr[i] != 0){
         cout << "Key: " << hashTable[i] << ", Value: " << arr[i] <<endl;
      }
   }
}

int main(){
   insert(3, 10);
   insert(13, 20);
   insert(23, 30);
   insert(33, 40);
   insert(43, 50);
   insert(53, 60);
   insert(63, 70);
   display();
   return 0;
}

输出

以下是上述 C++ 程序的输出：

Key: 3, Value: 10
Key: 13, Value: 20
Key: 23, Value: 30
Key: 33, Value: 40
Key: 43, Value: 50
Key: 53, Value: 60
Key: 63, Value: 70

// Java 程序，用于在 Hashed Array Tree 上执行插入操作
public class HashedArrayTree {
   static final int SIZE = 10;
   static int[] hashTable = new int[SIZE];
   static int[] arr = new int[SIZE];

   static int hashFunction(int key){
      return key % SIZE;
   }

   static void insert(int key, int value){
      int index = hashFunction(key);
      while(arr[index] != 0){
         index = (index + 1) % SIZE;
      }
      arr[index] = value;
      hashTable[index] = key;
   }

   static void display(){
      for(int i = 0; i < SIZE; i++){
         if(arr[i] != 0){
            System.out.println("Key: " + hashTable[i] + ", Value: " + arr[i]);
         }
      }
   }

   public static void main(String[] args){
      insert(3, 10);
      insert(13, 20);
      insert(23, 30);
      insert(33, 40);
      insert(43, 50);
      insert(53, 60);
      insert(63, 70);
      display();
   }
}

输出

以下是上述 Java 程序的输出：

Key: 3, Value: 10
Key: 13, Value: 20
Key: 23, Value: 30
Key: 33, Value: 40
Key: 43, Value: 50
Key: 53, Value: 60
Key: 63, Value: 70

# Python 程序，用于在 Hashed Array Tree 上执行插入操作
SIZE = 10
hashTable = [0] * SIZE
arr = [0] * SIZE

def hashFunction(key):
   return key % SIZE

def insert(key, value):
   index = hashFunction(key)
   while arr[index] != 0:
      index = (index + 1) % SIZE
   arr[index] = value
   hashTable[index] = key

def display():
   for i in range(SIZE):
      if arr[i] != 0:
         print("Key:", hashTable[i], ", Value:", arr[i])

insert(3, 10)
insert(13, 20)
insert(23, 30)
insert(33, 40)
insert(43, 50)
insert(53, 60)
insert(63, 70)
display()

输出

以下是上述 Python 程序的输出：

Key: 3, Value: 10
Key: 13, Value: 20
Key: 23, Value: 30
Key: 33, Value: 40
Key: 43, Value: 50
Key: 53, Value: 60
Key: 63, Value: 70

Hashed Array Tree 的获取操作算法

以下是在 Hashed Array Tree 上执行获取操作的算法 −

1.计算键的 hash 值。
2.从 hash table 中检索索引。
3.访问数组中检索到的索引处的元素。

获取操作的代码

以下是如何在 hashed array tree 中实现获取操作的示例：

C C++ Java Python 
// C 程序，用于在 Hashed Array Tree 上执行获取操作
#include <stdio.h>
#include <stdlib.h>

#define SIZE 10

int hashTable[SIZE] = {0};
int arr[SIZE] = {0};

int hashFunction(int key){
   return key % SIZE;
}

void insert(int key, int value){
   int index = hashFunction(key);
   while(arr[index] != 0){
      index = (index + 1) % SIZE;
   }
   arr[index] = value;
   hashTable[index] = key;
}

int get(int key){
   int index = hashFunction(key);
   while(hashTable[index] != key){
      index = (index + 1) % SIZE;
   }
   return arr[index];
}

int main(){
   insert(3, 10);
   insert(13, 20);
   insert(23, 30);
   insert(33, 40);
   insert(43, 50);
   insert(53, 60);
   insert(63, 70);
   insert(73, 80);
   insert(83, 90);
   insert(93, 100);
   printf("Value: %d\n", get(33));
   return 0;
}

输出

以下是上述 C 程序的输出：

Value: 40

// C++ 程序，用于在 Hashed Array Tree 上执行获取操作
#include <iostream>
using namespace std;

#define SIZE 10

int hashTable[SIZE] = {0};
int arr[SIZE] = {0};

int hashFunction(int key){
   return key % SIZE;
}

void insert(int key, int value){
   int index = hashFunction(key);
   while(arr[index] != 0){
      index = (index + 1) % SIZE;
   }
   arr[index] = value;
   hashTable[index] = key;
}

int get(int key){
   int index = hashFunction(key);
   while(hashTable[index] != key){
      index = (index + 1) % SIZE;
   }
   return arr[index];
}

int main(){
   insert(3, 10);
   insert(13, 20);
   insert(23, 30);
   insert(33, 40);
   insert(43, 50);
   insert(53, 60);
   insert(63, 70);
   insert(73, 80);
   insert(83, 90);
   insert(93, 100);
   cout << "Value: " << get(33) <<endl;
   return 0;
}

输出

以下是上述 C++ 程序的输出：

Value: 40

// Java 程序，用于在 Hashed Array Tree 上执行获取操作
public class HashedArrayTree {
   static final int SIZE = 10;
   static int[] hashTable = new int[SIZE];
   static int[] arr = new int[SIZE];

   static int hashFunction(int key){
      return key % SIZE;
   }

   static void insert(int key, int value){
      int index = hashFunction(key);
      while(arr[index] != 0){
         index = (index + 1) % SIZE;
      }
      arr[index] = value;
      hashTable[index] = key;
   }

   static int get(int key){
      int index = hashFunction(key);
      while(hashTable[index] != key){
         index = (index + 1) % SIZE;
      }
      return arr[index];
   }

   public static void main(String[] args){
      insert(3, 10);
      insert(13, 20);
      insert(23, 30);
      insert(33, 40);
      insert(43, 50);
      insert(53, 60);
      insert(63, 70);
      insert(73, 80);
      insert(83, 90);
      insert(93, 100);
      System.out.println("Value: " + get(33));
   }
}

输出

以下是上述 Java 程序的输出：

Value: 40

# Python 程序，用于在 Hashed Array Tree 上执行获取操作
SIZE = 10
hashTable = [0] * SIZE
arr = [0] * SIZE

def hashFunction(key):
   return key % SIZE

def insert(key, value):
    index = hashFunction(key)
    while arr[index] != 0:
        index = (index + 1) % SIZE
    arr[index] = value
    hashTable[index] = key

def get(key):
    index = hashFunction(key)
    while hashTable[index] != key:
        index = (index + 1) % SIZE
    return arr[index]

insert(3, 10)
insert(13, 20)
insert(23, 30)
insert(33, 40)
insert(43, 50)
insert(53, 60)
insert(63, 70)
insert(73, 80)
insert(83, 90)
insert(93, 100)
print("Value:", get(33))

输出

以下是上述 Python 程序的输出：

Value: 40

Hashed Array Tree 的删除操作算法

以下是在 Hashed Array Tree 上执行删除操作的算法 −

1.计算键的 hash 值。
2.从 hash table 中检索索引。
3.删除数组中检索到的索引处的元素。

删除操作的代码

以下是如何在 hashed array tree 中实现删除操作的示例：

C C++ Java Python 
// C 程序，用于在 Hashed Array Tree 上执行删除操作
#include <stdio.h>
#include <stdlib.h>

#define SIZE 10

int hashTable[SIZE] = {0};
int arr[SIZE] = {0};

int hashFunction(int key){
   return key % SIZE;
}

void insert(int key, int value){
   int index = hashFunction(key);
   while(arr[index] != 0){
      index = (index + 1) % SIZE;
   }
   arr[index] = value;
   hashTable[index] = key;
}

void deleteEl(int key){
   int index = hashFunction(key);
   while(hashTable[index] != key){
      index = (index + 1) % SIZE;
   }
   arr[index] = 0;
   hashTable[index] = 0;
}

void display(){
   for(int i = 0; i < SIZE; i++){
      if(arr[i] != 0){
         printf("Key: %d, Value: %d\n", hashTable[i], arr[i]);
      }
   }
}

int main(){
   insert(3, 10);
   insert(13, 20);
   insert(23, 30);
   insert(33, 40);
   insert(43, 50);
   insert(53, 60);
   printf("Before Deletion:\n");
   display();
   deleteEl(33);
   printf("After Deletion:\n");
   display();
   return 0;
}

输出

以下是上述 C 程序的输出：

Before Deletion
Key: 3, Value: 10
Key: 13, Value: 20
Key: 23, Value: 30
Key: 33, Value: 40
Key: 43, Value: 50
Key: 53, Value: 60
After Deletion
Key: 3, Value: 10
Key: 13, Value: 20
Key: 23, Value: 30
Key: 43, Value: 50
Key: 53, Value: 60

// C++ 程序，用于在 Hashed Array Tree 上执行删除操作
#include <iostream>
using namespace std;

#define SIZE 10

int hashTable[SIZE] = {0};
int arr[SIZE] = {0};

int hashFunction(int key){
   return key % SIZE;
}

void insert(int key, int value){
   int index = hashFunction(key);
   while(arr[index] != 0){
      index = (index + 1) % SIZE;
   }
   arr[index] = value;
   hashTable[index] = key;
}

void deleteEl(int key){
   int index = hashFunction(key);
   while(hashTable[index] != key){
      index = (index + 1) % SIZE;
   }
   arr[index] = 0;
   hashTable[index] = 0;
}

void display(){
   for(int i = 0; i < SIZE; i++){
      if(arr[i] != 0){
         cout << "Key: " << hashTable[i] << ", Value: " << arr[i] <<endl;
      }
   }
}

int main(){
   insert(3, 10);
   insert(13, 20);
   insert(23, 30);
   insert(33, 40);
   insert(43, 50);
   insert(53, 60);
   cout << "Before Deletion:" <<endl;
   display();
   deleteEl(33);
   cout << "After Deletion:" <<endl;
   display();
   return 0;
}

输出

以下是上述 C++ 程序的输出：

Before Deletion:
Key: 3, Value: 10
Key: 13, Value: 20
Key: 23, Value: 30
Key: 33, Value: 40
Key: 43, Value: 50
Key: 53, Value: 60
After Deletion:
Key: 3, Value: 10
Key: 13, Value: 20
Key: 23, Value: 30
Key: 43, Value: 50
Key: 53, Value: 60

// Java 程序，用于在 Hashed Array Tree 上执行删除操作

public class HashedArrayTree {
   static final int SIZE = 10;
   static int[] hashTable = new int[SIZE];
   static int[] arr = new int[SIZE];

   static int hashFunction(int key){
      return key % SIZE;
   }

   static void insert(int key, int value){
      int index = hashFunction(key);
      while(arr[index] != 0){
         index = (index + 1) % SIZE;
      }
      arr[index] = value;
      hashTable[index] = key;
   }

   static void deleteEl(int key){
      int index = hashFunction(key);
      while(hashTable[index] != key){
         index = (index + 1) % SIZE;
      }
      arr[index] = 0;
      hashTable[index] = 0;
   }

   static void display(){
      for(int i = 0; i < SIZE; i++){
         if(arr[i] != 0){
            System.out.println("Key: " + hashTable[i] + ", Value: " + arr[i]);
         }
      }
   }

   public static void main(String[] args){
      insert(3, 10);
      insert(13, 20);
      insert(23, 30);
      insert(33, 40);
      insert(43, 50);
      insert(53, 60);
      System.out.println("Before Deletion:");
      display();
      deleteEl(33);
      System.out.println("After Deletion:");
      display();
   }
}

输出

以下是上述 Java 程序的输出：

Before Deletion:
Key: 3, Value: 10
Key: 13, Value: 20
Key: 23, Value: 30
Key: 33, Value: 40
Key: 43, Value: 50
Key: 53, Value: 60
After Deletion:
Key: 3, Value: 10
Key: 13, Value: 20
Key: 23, Value: 30
Key: 43, Value: 50
Key: 53, Value: 60

# Python 程序，用于在 Hashed Array Tree 上执行删除操作
SIZE = 10
hashTable = [0] * SIZE
arr = [0] * SIZE

def hashFunction(key):
   return key % SIZE

def insert(key, value):
   index = hashFunction(key)
   while arr[index] != 0:
       index = (index + 1) % SIZE
   arr[index] = value
   hashTable[index] = key

def deleteEl(key):
   index = hashFunction(key)
   while hashTable[index] != key:
      index = (index + 1) % SIZE
   arr[index] = 0
   hashTable[index] = 0

def display():
   for i in range(SIZE):
      if arr[i] != 0:
         print("Key:", hashTable[i], ", Value:", arr[i])

insert(3, 10)
insert(13, 20)
insert(23, 30)
insert(33, 40)
insert(43, 50)
insert(53, 60)
print("Before Deletion:")
display()
deleteEl(33)
print("After Deletion:")
display()

输出

以下是上述 Python 程序的输出：

Before Deletion:
Key: 3, Value: 10
Key: 13, Value: 20
Key: 23, Value: 30
Key: 33, Value: 40
Key: 43, Value: 50
Key: 53, Value: 60
After Deletion:
Key: 3, Value: 10   
Key: 13, Value: 20
Key: 23, Value: 30
Key: 43, Value: 50
Key: 53, Value: 60

Hashed Array Tree 的时间复杂度

hashed array tree 操作的时间复杂度如下：

  • 插入操作：插入操作的平均时间复杂度为 O(1)，因为 hash function 提供了常量时间的数组索引访问。
  • 获取操作：获取操作的平均时间复杂度为 O(1)，因为 hash function 提供了常量时间的数组索引访问。
  • 删除操作：删除操作的平均时间复杂度为 O(1)，因为 hash function 提供了常量时间的数组索引访问。

Hashed Array Tree 的应用

hashed array tree 用于以下应用：

  • 数据库管理：hashed array tree 用于在数据库中存储和管理数据。
  • 缓存管理：它用于高效地存储和管理缓存数据。
  • 文件系统：hashed array tree 用于存储和管理文件系统数据。
  • 索引：它用于创建快速数据检索的索引。
  • 内存管理：hashed array tree 用于高效管理内存。

结论

在本章中，我们学习了数据结构中的 hashed array tree。我们讨论了 hashed array tree 的工作原理、其操作、实现以及时间复杂度。我们还看到了在 C、C++、Java 和 Python 中对 hashed array tree 进行的 insert、get 和 delete 操作的示例。Hashed array tree 是一种强大的数据结构，它提供了对元素的 快速访问 和 高效内存使用。