二次プロービング（Quadratic Probing）でハッシュテーブルを実装するC++プログラム

ハッシュテーブルは、キーと値のペアを格納するためのデータ構造です。ハッシュテーブルでは、ハッシュ関数を使って配列のインデックスを計算し、その位置へ要素を挿入または検索します。

二次プロービング（Quadratic Probing）は、オープンアドレス法のハッシュテーブルにおける衝突解決手法の一つです。元のハッシュインデックスに対して、二次多項式から得られる間隔（1, 3, 5, 7, …と増加する値）を順次加算しながら探査を進め、空きスロットが見つかるまで処理を繰り返します。線形プロービングで問題となる一次クラスタリング（データが特定領域に集中する現象）を緩和できる点が特徴です。

本記事では、二次プロービングを用いてハッシュテーブルを実装するC++プログラムを解説します。

アルゴリズム

キー値の検索

開始
　関数 SearchKey(int k, HashTable *ht) を宣言
　　int pos = HashFunc(k, ht->s)
　　collisions（衝突回数）を 0 で初期化
　　while (ht->t[pos].info != Emp かつ ht->t[pos].e != k)
　　　　pos = pos + 2 * ++collisions - 1
　　　　if (pos >= ht->s)
　　　　　　pos = pos - ht->s
　　return pos
終了

挿入

開始
　関数 Insert(int k, HashTable *ht) を宣言
　　int pos = SearchKey(k, ht)
　　if (ht->t[pos].info != Legi)
　　　　ht->t[pos].info = Legi
　　　　ht->t[pos].e = k
終了

表示

開始
　関数 display(HashTable *ht) を宣言
　　for (int i = 0; i < ht->s; i++)
　　　　int value = ht->t[i].e
　　　　if (!value)
　　　　　　「Position: 」と現在の位置を出力
　　　　　　「Element: Null」と出力
　　　　else
　　　　　　「Position: 」と現在の位置を出力
　　　　　　「Element: 」と要素の値を出力
終了

再ハッシュ関数

開始
　関数 Rehash(HashTable *ht) を宣言
　　int s = ht->s
　　HashTableEntry *t = ht->t
　　ht = initiateTable(2 * s)
　　for (int i = 0; i < s; i++)
　　　　if (t[i].info == Legi)
　　　　　　Insert(t[i].e, ht)
　　free(t)
　　return ht
終了

サンプルコード

#include <iostream>
#include <cstdlib>
#define T_S 10
using namespace std;
enum EntryType {
    Legi, Emp, Del};
    struct HashTableEntry {
        int e;
        enum EntryType info;
    };
    struct HashTable {
        int s;
        HashTableEntry *t;
    };
    bool isPrime (int n) {
    if (n == 2 || n == 3)
        return true;
    if (n == 1 || n % 2 == 0)
        return false;
    for (int i = 3; i * i <= n; i += 2)
        if (n % i == 0)
            return false;
    return true;
}
int nextPrime(int n) {
    if (n <= 0)
        n == 3;
    if (n % 2 == 0)
        n++;
    for (; !isPrime( n ); n += 2);
        return n;
}
int HashFunc(int k, int s) {
    return k % s;
}
HashTable *initiateTable(int s) {
    HashTable *ht;
    if (s < T_S) {
        cout<<"Table Size is Too Small"<<endl;
        return NULL;
    }
    ht= new HashTable;
    if (ht == NULL) {
        cout<<"Out of Space"<<endl;
        return NULL;
    }
    ht->s = nextPrime(s);
    ht->t = new HashTableEntry [ht->s];
    if (ht->t == NULL) {
        cout<<"Table Size is Too Small"<<endl;
        return NULL;
    }
    for (int i = 0; i < ht->s; i++) {
        ht->t[i].info = Emp;
        ht->t[i].e = NULL;
    }
    return ht;
}
int SearchKey(int k, HashTable *ht) {
    int pos = HashFunc(k, ht->s);
    int collisions = 0;
    while (ht->t[pos].info != Emp && ht->t[pos].e != k) {
        pos = pos + 2 * ++collisions -1;
        if (pos >= ht->s)
            pos = pos - ht->s;
    }
    return pos;
}
void Insert(int k, HashTable *ht) {
    int pos = SearchKey(k, ht);
    if (ht->t[pos].info != Legi) {
        ht->t[pos].info = Legi;
        ht->t[pos].e = k;
    }
}
HashTable *Rehash(HashTable *ht) {
    int s = ht->s;
    HashTableEntry *t= ht->t;
    ht= initiateTable(2 * s);
    for (int i = 0; i < s; i++) {
        if (t[i].info == Legi)
            Insert(t[i].e, ht);
    }
    free(t);
    return ht;
}
void display(HashTable *ht) {
    for (int i = 0; i < ht->s; i++) {
        int value = ht->t[i].e;
        if (!value)
            cout<<"Position: "<<i + 1<<" Element: Null"<<endl;
        else
            cout<<"Position: "<<i + 1<<" Element: "<<value<<endl;
    }
}
int main() {
    int v, s, pos, i = 1;
    int c;
    HashTable *ht;
    while(1) {
        cout<<"1.Initialize size of the table"<<endl;
        cout<<"2.Insert element into the table"<<endl;
        cout<<"3.Display Hash Table"<<endl;
        cout<<"4.Rehash The Table"<<endl;
        cout<<"5.Exit"<<endl;
        cout<<"Enter your choice: ";
        cin>>c;
        switch(c) {
            case 1:
                cout<<"Enter size of the Hash Table: ";
                cin>>s;
                ht = initiateTable(s);
                cout<<"Size of Hash Table: "<<nextPrime(s);
            break;
            case 2:
                if (i > ht->s) {
                    cout<<"Table is Full, Rehash the table"<<endl;
                    continue;
                }
                cout<<"Enter element to be inserted: ";
                cin>>v;
                Insert(v, ht);
                i++;
            break;
            case 3:
                display(ht);
            break;
            case 4:
                ht = Rehash(ht);
            break;
            case 5:
                exit(1);
            default:
                cout<<"
Enter correct option
";
        }
    }
    return 0;
}

実行結果

1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 1
Enter size of the Hash Table: 4
Table Size is Too Small
Size of Hash Table: 51.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 1
Enter size of the Hash Table: 10
Size of Hash Table: 111.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 1
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 2
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 3
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 4
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 5
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 6
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 7
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 8
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 9
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 10
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 11
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Table is Full, Rehash the table
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 3
Position: 1 Element: 11
Position: 2 Element: 1
Position: 3 Element: 2
Position: 4 Element: 3
Position: 5 Element: 4
Position: 6 Element: 5
Position: 7 Element: 6
Position: 8 Element: 7
Position: 9 Element: 8
Position: 10 Element: 9
Position: 11 Element: 10
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 4
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 3
Position: 1 Element: Null
Position: 2 Element: 1
Position: 3 Element: 2
Position: 4 Element: 3
Position: 5 Element: 4
Position: 6 Element: 5
Position: 7 Element: 6
Position: 8 Element: 7
Position: 9 Element: 8
Position: 10 Element: 9
Position: 11 Element: 10
Position: 12 Element: 11
Position: 13 Element: Null
Position: 14 Element: Null
Position: 15 Element: Null
Position: 16 Element: Null
Position: 17 Element: Null
Position: 18 Element: Null
Position: 19 Element: Null
Position: 20 Element: Null
Position: 21 Element: Null
Position: 22 Element: Null
Position: 23 Element: Null
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 20
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 5

C++のコンストラクタから例外をスローする方法とデストラクタの挙動

C++で可変数の引数（可変長引数）を扱う方法

C++で基数ソート（ラディックスソート）を実装するプログラム
基数ソート（ラディックスソート）は、非比較型のソートアルゴリズムの一つです。要素同士を直接比較するのではなく、整数キーを構成する各桁に注目し、同じ桁位置・同じ値を持つ数字どうしをグループ化しながら並べ替えを行います。「基数」とは記数法における底のことです。私たちが普段使う10進法では基数は10であるため、10進数を基数ソートで並べ替える際には、数値を一時的に格納するための10個のバケット（ポケット）が必要になります。基数ソートの計算量時間計算量： O(nk)　※nは要素数、kは最大桁数空間計算量： O(n+k) 入力 − ソート前のデータ： 802 630 20 745 52 3
C++でクイックソートを実装するプログラム|ランダム化で最悪ケースO(n²)を回避
クイックソート(Quick Sort)は「分割統治法(divide-and-conquer)」に基づく高速な整列アルゴリズムです。平均時間計算量は O(n log n) と非常に効率的ですが、ピボットの選び方次第では最悪ケースで O(n²) まで計算量が悪化する可能性があります。そこで本記事では、乱数を用いてピボットをランダムに選択する「ランダム化クイックソート」をC++で実装し、最悪ケースが発生する確率を大幅に下げる方法を解説します。アルゴリズム Partition(int a[], int l, int h) 配列 a の範囲 [l, h] を、ピボットより小さいグループと大きい