質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.35%
ハッシュマップ

ハッシュ関数を用いてキーを関連する値にマッピングするデータ構造です。

ハッシュ

ハッシュは、高速にデータ検索を行うアルゴリズムのことです。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

Q&A

2回答

2165閲覧

c++でハッシュテーブルを実装したいです。

saunashio

総合スコア6

ハッシュマップ

ハッシュ関数を用いてキーを関連する値にマッピングするデータ構造です。

ハッシュ

ハッシュは、高速にデータ検索を行うアルゴリズムのことです。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

0グッド

0クリップ

投稿2021/06/11 09:08

c++でハッシュテーブルを実装したいです

こちら

を参考にして、ハッシュテーブルを実装しています。
リンク先のコードは正しく動くのですが、これをintではなく、charで実装したいです

ソースコードを
int k-> char k
int v ->char v
と安直に変更すると、「コンパイルは通りますが、正しく挙動しません」
型を変えたことによって他にも変えるべきところがあるのだと推察しておりますが、詳しく分かりません。(ハッシュ関数の計算の部分でしょうか?)
ご教授頂けましたら幸いです。

発生している問題・エラーメッセージ

文字列を入力するとメッセージが止まらず、無限に流れている。

該当のソースコード

c++

1#include<iostream> 2#include<cstdlib> 3#include<string> 4#include<cstdio> 5using namespace std; 6const int T_S = 200; 7class HashTableEntry { 8 public: 9 char k; 10 char v; 11 HashTableEntry(char k, char v) { 12 this->k= k; 13 this->v = v; 14 } 15}; 16class HashMapTable { 17 private: 18 HashTableEntry **t; 19 public: 20 HashMapTable() { 21 t = new HashTableEntry * [T_S]; 22 for (int i = 0; i< T_S; i++) { 23 t[i] = NULL; 24 } 25 } 26 int HashFunc(char k) { 27 return (k % T_S); 28 } 29 void Insert(char k, char v) { 30 int h = HashFunc(k); 31 while (t[h] != NULL && t[h]->k != k) { 32 h = HashFunc(h + 1); 33 } 34 if (t[h] != NULL) 35 delete t[h]; 36 t[h] = new HashTableEntry(k, v); 37 } 38 int SearchKey(char k) { 39 int h = HashFunc(k); 40 while (t[h] != NULL && t[h]->k != k) { 41 h = HashFunc(h + 1); 42 } 43 if (t[h] == NULL) 44 return -1; 45 else 46 return t[h]->v; 47 } 48 void Remove(char k) { 49 int h = HashFunc(k); 50 while (t[h] != NULL) { 51 if (t[h]->k == k) 52 break; 53 h = HashFunc(h + 1); 54 } 55 if (t[h] == NULL) { 56 cout<<"No Element found at key "<<k<<endl; 57 return; 58 } else { 59 delete t[h]; 60 } 61 cout<<"Element Deleted"<<endl; 62 } 63 ~HashMapTable() { 64 for (int i = 0; i < T_S; i++) { 65 if (t[i] != NULL) 66 delete t[i]; 67 delete[] t; 68 } 69 } 70}; 71int main() { 72 HashMapTable hash; 73 char k, v; 74 int c; 75 while (1) { 76 cout<<"1.Insert element into the table"<<endl; 77 cout<<"2.Search element from the key"<<endl; 78 cout<<"3.Delete element at a key"<<endl; 79 cout<<"4.Exit"<<endl; 80 cout<<"Enter your choice: "; 81 cin>>c; 82 switch(c) { 83 case 1: 84 cout<<"Enter element to be inserted: "; 85 cin>>v; 86 cout<<"Enter key at which element to be inserted: "; 87 cin>>k; 88 hash.Insert(k, v); 89 break; 90 case 2: 91 cout<<"Enter key of the element to be searched: "; 92 cin>>k; 93 if (hash.SearchKey(k) == -1) { 94 cout<<"No element found at key "<<k<<endl; 95 continue; 96 } else { 97 cout<<"Element at key "<<k<<" : "; 98 cout<<hash.SearchKey(k)<<endl; 99 } 100 break; 101 case 3: 102 cout<<"Enter key of the element to be deleted: "; 103 cin>>k; 104 hash.Remove(k); 105 break; 106 case 4: 107 exit(1); 108 default: 109 cout<<"\nEnter correct option\n"; 110 } 111 } 112 return 0; 113}

試したこと

int k-> char k
int v ->char v
と変更してみた。

補足情報(FW/ツールのバージョンなど)

ここにより詳細な情報を記載してください。

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

asm

2021/06/11 10:13

> 文字列を入力するとメッセージが止まらず、無限に流れている。 具体的に何を入力したのでしょうか? charなのですからk,vともに1文字までしか入りませんよね?
saunashio

2021/06/12 01:17

ご返信ありがとうございます。 charを数文字入れました。 そうでした、charの配列にしてみます。
guest

回答2

0

多くの環境で、char符号付きの8ビットなので、値の範囲は-128~+127までです。「200で割ったあまり」すら、正しく表せないことがありますので、それが影響しているかもしれません。

投稿2021/06/11 09:26

maisumakun

総合スコア146018

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

saunashio

2021/06/12 01:15

ありがとうございます。200を変更してみます
guest

0

アドバイスも踏まえ、ポインタを使い実現できそうです。
皆様ありがとうございました。

c++#include

1#include <cstdlib> 2#include <string> 3#include <cstdio> 4using namespace std; 5const int T_S = 107; 6class HashTableEntry 7{ 8public: 9 char *k; 10 char *v; 11 HashTableEntry(char *k, char *v) 12 { 13 this->k = k; 14 this->v = v; 15 } 16}; 17class HashMapTable 18{ 19private: 20 HashTableEntry **t; 21 22public: 23 HashMapTable() 24 { 25 t = new HashTableEntry *[T_S]; 26 for (int i = 0; i < T_S; i++) 27 { 28 t[i] = NULL; 29 } 30 } 31 int HashFunc(char *key) 32 { 33 int i = 0; 34 int s = 1; 35 while (*key != 0) 36 { 37 i += *key; 38 key++; 39 } 40 return (i % T_S); 41 } 42 void Insert(char *k, char *v) 43 { 44 int h = HashFunc(k); 45 46 if (t[h] != NULL) 47 delete t[h]; 48 t[h] = new HashTableEntry(k, v); 49 } 50 char *SearchKey(char *k) 51 { 52 int h = HashFunc(k); 53 54 if (t[h] == NULL) 55 return NULL; 56 else 57 return t[h]->v; 58 } 59 void Remove(char *k) 60 { 61 int h = HashFunc(k); 62 if (t[h] == NULL) 63 { 64 cout << "No Element found at key " << k << endl; 65 return; 66 } 67 else 68 { 69 delete t[h]; 70 } 71 cout << "Element Deleted" << endl; 72 } 73 ~HashMapTable() 74 { 75 for (int i = 0; i < T_S; i++) 76 { 77 if (t[i] != NULL) 78 delete t[i]; 79 delete[] t; 80 } 81 } 82}; 83int main() 84{ 85 HashMapTable hash; 86 char k[200]; 87 char v[200]; 88 int c; 89 while (1) 90 { 91 cout << "1.Insert element into the table" << endl; 92 cout << "2.Search element from the key" << endl; 93 cout << "3.Delete element at a key" << endl; 94 cout << "4.Exit" << endl; 95 cout << "Enter your choice: "; 96 cin >> c; 97 switch (c) 98 { 99 case 1: 100 cout << "Enter element to be inserted: "; 101 cin >> v; 102 cout << "Enter key at which element to be inserted: "; 103 cin >> k; 104 hash.Insert(k, v); 105 break; 106 case 2: 107 cout << "Enter key of the element to be searched: "; 108 cin >> k; 109 if (hash.SearchKey(k) == NULL) 110 { 111 cout << "No element found at key " << k << endl; 112 continue; 113 } 114 else 115 { 116 cout << "Element at key " << k << " : "; 117 cout << hash.SearchKey(k) << endl; 118 } 119 break; 120 case 3: 121 cout << "Enter key of the element to be deleted: "; 122 cin >> k; 123 hash.Remove(k); 124 break; 125 case 4: 126 exit(1); 127 default: 128 cout << "\nEnter correct option\n"; 129 } 130 } 131 return 0; 132}

投稿2021/06/12 01:44

編集2021/06/12 02:07
saunashio

総合スコア6

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

asm

2021/06/12 02:13

k,vがchar*なので、もとの変数が解放されると不正なポインタになる SearchKeyにてkの同一性を検証していないのでハッシュ(107種類)が同一だと誤ったvを取得する といった問題があります。 実際に使うのであれば #include<unordered_map> std::unordered_map<std::string, std::string> hash; となります。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

まだベストアンサーが選ばれていません

会員登録して回答してみよう

アカウントをお持ちの方は

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.35%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問