ハッシュ探索(Hash Search)
ハッシュテーブルを用意し、
テーブル上のインデックスをハッシュ関数で作成する。
ハッシュ関数はデータを受け、インデックスを返す。
探索にかかる時間はハッシュ関数がハッシュ、すなわちテーブルのインデックスをつくるにかかる時間だけである。
ただしハッシュが衝突したらそこから線形サーチに移行したりする。
以下GPT4o
基本概念
ハッシュ探索は、データの格納と検索を効率的に行うためのアルゴリズムとデータ構造の一種です。ハッシュテーブルとも呼ばれ、特に大規模なデータセットに対して高速な検索が求められる場合に使用されます。以下に、ハッシュ探索の基本的な概念と仕組みを説明します。
ハッシュ関数：
ハッシュ関数は、入力データ（キー）を一定の範囲の数値（ハッシュ値）に変換する関数です。このハッシュ値を利用して、データをハッシュテーブル内の特定の位置に格納します。
ハッシュテーブル：
ハッシュテーブルは、データを格納するための配列です。各配列の位置（インデックス）は、ハッシュ関数によって計算されたハッシュ値に対応します。
衝突（コリジョン）：
異なるキーが同じハッシュ値を持つ場合、これを衝突（コリジョン）と言います。衝突が発生した場合、ハッシュテーブル内でのデータの格納と検索が複雑になります。
衝突解決法
ハッシュ探索では、衝突を解決するためのいくつかの方法が存在します。代表的な方法をいくつか紹介します。
チェイン法（連鎖法）：
衝突が発生した場合、ハッシュテーブルの各位置にリンクリスト（連結リスト）を用意し、同じハッシュ値を持つデータをそのリンクリストに格納します。
オープンアドレッシング：
衝突が発生した場合、別の空いている位置を探してデータを格納します。代表的な手法には以下のものがあります。
線形探査：次の空いている位置を順番に探します。
二次探査：二次関数のステップで位置を探します。
二重ハッシュ法：別のハッシュ関数を使って新しい位置を計算します。
利点と欠点
利点：
平均的な場合、データの格納と検索が非常に高速です（O(1)の時間複雑度）。
大規模なデータセットに対しても効率的に動作します。
欠点：
衝突が頻発すると性能が低下します。
ハッシュ関数の設計が難しい場合があります。
データの削除が複雑になることがあります。
具体例
例えば、名前と電話番号をハッシュテーブルに格納する場合を考えてみましょう。以下のように動作します。
名前をキーとしてハッシュ関数に入力し、ハッシュ値を計算します。
計算されたハッシュ値に対応する位置に電話番号を格納します。
検索する際は、名前を再びハッシュ関数に入力し、対応する位置を確認して電話番号を取得します。
このように、ハッシュ探索は非常に効率的なデータ構造とアルゴリズムであり、データベースやキャッシュなど多くのアプリケーションで広く使用されています。
C
#include <stdio.h>
#include <stdlib.h>
#define SIZE 10
struct Node {
int data;
struct Node* next;
};
struct Node* hashTable[SIZE];
int hashFunction(int key) {
return key % SIZE;
}
void insert(int key) {
int hashIndex = hashFunction(key);
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = key;
newNode->next = hashTable[hashIndex];
hashTable[hashIndex] = newNode;
}
int search(int key) {
int hashIndex = hashFunction(key);
struct Node* temp = hashTable[hashIndex];
while (temp) {
if (temp->data == key) {
return 1;
}
temp = temp->next;
}
return 0;
}
int main() {
for (int i = 0; i < SIZE; i++) {
hashTable[i] = NULL;
}
insert(5);
insert(15);
insert(25);
printf(search(15) ? "Element found\n" : "Element not found\n");
printf(search(7) ? "Element found\n" : "Element not found\n");
return 0;
}
C++
#include <iostream>
#include <list>
using namespace std;
class HashTable {
int BUCKET;
list<int>* table;
public:
HashTable(int V);
void insertItem(int x);
bool searchItem(int x);
int hashFunction(int x) { return (x % BUCKET); }
};
HashTable::HashTable(int b) {
BUCKET = b;
table = new list<int>[BUCKET];
}
void HashTable::insertItem(int key) {
int index = hashFunction(key);
table[index].push_back(key);
}
bool HashTable::searchItem(int key) {
int index = hashFunction(key);
for (auto x : table[index]) {
if (x == key) {
return true;
}
}
return false;
}
int main() {
HashTable h(7);
h.insertItem(15);
h.insertItem(11);
h.insertItem(27);
cout << (h.searchItem(15) ? "Element found" : "Element not found") << endl;
cout << (h.searchItem(10) ? "Element found" : "Element not found") << endl;
return 0;
}
C#
using System;
using System.Collections.Generic;
class HashTable {
private readonly int BUCKET;
private readonly List<int>[] table;
public HashTable(int b) {
BUCKET = b;
table = new List<int>[BUCKET];
for (int i = 0; i < BUCKET; i++) {
table[i] = new List<int>();
}
}
public void InsertItem(int key) {
int index = key % BUCKET;
table[index].Add(key);
}
public bool SearchItem(int key) {
int index = key % BUCKET;
return table[index].Contains(key);
}
}
class Program {
static void Main() {
HashTable h = new HashTable(7);
h.InsertItem(15);
h.InsertItem(11);
h.InsertItem(27);
Console.WriteLine(h.SearchItem(15) ? "Element found" : "Element not found");
Console.WriteLine(h.SearchItem(10) ? "Element found" : "Element not found");
}
}
Java
import java.util.LinkedList;
class HashTable {
private final int BUCKET;
private final LinkedList<Integer>[] table;
public HashTable(int b) {
BUCKET = b;
table = new LinkedList[b];
for (int i = 0; i < b; i++) {
table[i] = new LinkedList<>();
}
}
public void insertItem(int key) {
int index = key % BUCKET;
table[index].add(key);
}
public boolean searchItem(int key) {
int index = key % BUCKET;
return table[index].contains(key);
}
}
public class Main {
public static void main(String[] args) {
HashTable h = new HashTable(7);
h.insertItem(15);
h.insertItem(11);
h.insertItem(27);
System.out.println(h.searchItem(15) ? "Element found" : "Element not found");
System.out.println(h.searchItem(10) ? "Element found" : "Element not found");
}
}
Python
class HashTable:
def __init__(self, size):
self.size = size
self.table = [[] for _ in range(size)]
def hash_function(self, key):
return key % self.size
def insert_item(self, key):
index = self.hash_function(key)
self.table[index].append(key)
def search_item(self, key):
index = self.hash_function(key)
return key in self.table[index]
hash_table = HashTable(7)
hash_table.insert_item(15)
hash_table.insert_item(11)
hash_table.insert_item(27)
print("Element found" if hash_table.search_item(15) else "Element not found")
print("Element found" if hash_table.search_item(10) else "Element not found")
JavaScript
class HashTable {
constructor(size) {
this.size = size;
this.table = new Array(size).fill(null).map(() => []);
}
hashFunction(key) {
return key % this.size;
}
insertItem(key) {
const index = this.hashFunction(key);
this.table[index].push(key);
}
searchItem(key) {
const index = this.hashFunction(key);
return this.table[index].includes(key);
}
}
const hashTable = new HashTable(7);
hashTable.insertItem(15);
hashTable.insertItem(11);
hashTable.insertItem(27);
console.log(hashTable.searchItem(15) ? "Element found" : "Element not found");
console.log(hashTable.searchItem(10) ? "Element found" : "Element not found");
この記事が気に入ったらサポートをしてみませんか？