常連

### c++でハッシュテーブルを実装したいです
[こちら](https://www.tutorialspoint.com/cplusplus-program-to-implement-hash-tables)

を参考にして、ハッシュテーブルを実装しています。
リンク先のコードは正しく動くのですが、**これをintではなく、charで実装したいです**。

ソースコードを
int k-> char k
int v ->char v
と安直に変更すると、「コンパイルは通りますが、正しく挙動しません」
型を変えたことによって他にも変えるべきところがあるのだと推察しておりますが、詳しく分かりません。（ハッシュ関数の計算の部分でしょうか？）
ご教授頂けましたら幸いです。 

### 発生している問題・エラーメッセージ

```
文字列を入力するとメッセージが止まらず、無限に流れている。
```

### 該当のソースコード

```c++
#include<iostream>
#include<cstdlib>
#include<string>
#include<cstdio>
using namespace std;
const int T_S = 200;
class HashTableEntry {
   public:
      char k;
      char v;
      HashTableEntry(char k, char v) {
         this->k= k;
         this->v = v;
      }
};
class HashMapTable {
   private:
      HashTableEntry **t;
   public:
      HashMapTable() {
         t = new HashTableEntry * [T_S];
         for (int i = 0; i< T_S; i++) {
            t[i] = NULL;
         }
      }
      int HashFunc(char k) {
          return (k % T_S);
      }
      void Insert(char k, char v) {
         int h = HashFunc(k);
         while (t[h] != NULL && t[h]->k != k) {
            h = HashFunc(h + 1);
         }
         if (t[h] != NULL)
            delete t[h];
         t[h] = new HashTableEntry(k, v);
      }
      int SearchKey(char k) {
         int h = HashFunc(k);
         while (t[h] != NULL && t[h]->k != k) {
            h = HashFunc(h + 1);
         }
         if (t[h] == NULL)
            return -1;
         else
            return t[h]->v;
      }
      void Remove(char k) {
         int h = HashFunc(k);
         while (t[h] != NULL) {
            if (t[h]->k == k)
               break;
            h = HashFunc(h + 1);
         }
         if (t[h] == NULL) {
            cout<<"No Element found at key "<<k<<endl;
            return;
         } else {
            delete t[h];
         }
         cout<<"Element Deleted"<<endl;
      }
      ~HashMapTable() {
         for (int i = 0; i < T_S; i++) {
            if (t[i] != NULL)
               delete t[i];
               delete[] t;
         }
      }
};
int main() {
   HashMapTable hash;
   char k, v;
   int c;
   while (1) {
      cout<<"1.Insert element into the table"<<endl;
      cout<<"2.Search element from the key"<<endl;
      cout<<"3.Delete element at a key"<<endl;
      cout<<"4.Exit"<<endl;
      cout<<"Enter your choice: ";
      cin>>c;
      switch(c) {
         case 1:
            cout<<"Enter element to be inserted: ";
            cin>>v;
            cout<<"Enter key at which element to be inserted: ";
            cin>>k;
            hash.Insert(k, v);
         break;
         case 2:
            cout<<"Enter key of the element to be searched: ";
            cin>>k;
            if (hash.SearchKey(k) == -1) {
               cout<<"No element found at key "<<k<<endl;
               continue;
            } else {
               cout<<"Element at key "<<k<<" : ";
               cout<<hash.SearchKey(k)<<endl;
            }
         break;
         case 3:
            cout<<"Enter key of the element to be deleted: ";
            cin>>k;
            hash.Remove(k);
         break;
         case 4:
            exit(1);
         default:
            cout<<"\nEnter correct option\n";
      }
   }
   return 0;
}
```

### 試したこと
int k-> char k
int v ->char v
と変更してみた。
### 補足情報（FW/ツールのバージョンなど）

ここにより詳細な情報を記載してください。

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

```go
import "net/url"
u, _ := url.Parse("https://xxx.com?a=AAA&b=BBB&c=CCC&d=DDD")
query := u.Query()
// query -> map[a:[AAA] b:[BBB] c:[CCC] d:[DDD]]
```

Parse()はmap[string][]string型を返すらしいのですが、上記の場合,単なるstringでよい気がします。
Parse()が返すマップの要素を[]string型にしているメリットはあるのですか？

golangのurl.Parse()について

ハッシュ法で配列変数の格納をしたいのです。showArrayメソッドを追加して以下の実行を得たいのですがどうすればよいでしょうか？showArrayメソッドの作り方がわかりません。
[0] : 0
[1] : 0
[2] : 0
[3] : 0
[4] : 0
[5] : 1 (apple,180)
[6] : 1 (orange,90)
[7] : 0
[8] : 0
[9] : 2 (raspberry,830)->(blueberry,530)
[10] : 0
[11] : 1 (water melon,900)
[12] : 0

```Java
package exer3.hash;
import exer3.linkedStructure.LinkedList;
import java.util.ArrayList;

public class FruitHash {
    private class Pair {
    String key;
    Integer value;
    Pair(String key, Integer value) {
    this.key = key;
    this.value = value;
    }
@Override
public boolean equals(Object obj) {
    return obj.equals(key);
    }
Integer getValue() { return value; }
} 

    private ArrayList<LinkedList<Pair>> headers;
    private int arraySize;
    public FruitHash() { this(13); }

    public FruitHash(int size) {
    headers = new ArrayList<>();
    arraySize = size;
    for (int i = 0; i < size; i += 1)
        headers.add(new LinkedList<>());
    }
    public FruitHash put(String key, Integer value) {
    int idx = hashFunction(key) % arraySize;
    headers.get(idx).insertA(new Pair(key, value));
    return this;
        }
    public Integer get(String key) {
    int idx = hashFunction(key) % arraySize;
    LinkedList<Pair> h = headers.get(idx);
    LinkedList<Pair>.Node n = h.search(new Pair(key, null));
    Pair p = h.get(n);
    return (null == p ? null : p.getValue());
    }

    public int hashFunction(String key) {
    return key.length();
        }

    public void showArray(int size){
        
            }
         }
    }


package exer3.hash.tester;
import exer3.hash.FruitHash;
public class TesterH04 {
public static void main(String[] args) {
FruitHash fh = new FruitHash();
fh.put("apple", 180);
fh.put("orange", 90);
fh.put("water melon", 900);
fh.put("blueberry", 530);
fh.put("raspberry", 830);
fh.showArray();
    }
}
```

ハッシュ法の配列変数の格納

ハッシュテーブルを用いて英和辞典を作成するプログラムをCで書いています。
コードは以下の通りです。
```C
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

#define NEW(p, n){p = malloc((n)*sizeof(p[0]));}

typedef char* String;
//後々使いやすくするため、ここでStringタイプを定義しちゃいます

//英和辞書用のオブジェクトです(英語の見出しと日本語の意味のペア)
typedef struct slobj_{
    struct slobj_* next;
    String key;
    String jpn;
}* slobj;

//連結リスト
typedef struct{
    slobj head;
    slobj tail;
}* slist;

typedef struct{
    int n; //ハッシュに格納されている要素数
    int m; //ハッシュ表のサイズ
    slist* T; //リストの配列
} hash;

//ハッシュ関数
int hfunc(hash H, String key){
    int h=0, i=0;
    while (key[i] != 0){
        h = h*101+key[i]; //ハッシュ値を計算
        i++;
    }
    return abs(h) % H.m; //非負の値にして、表のサイズで割った余り
}

//文字列の長さを求める
int string_len(String str){
    int len=0;
    while(str[len]!=0){
        len++;
    }
    return len;
}

//文字列を標準入力から読む
String string_input(void){
    int i, len;
    char buf[1000];
    String str;
    scanf("%999s", buf);

    len = string_len(buf);

    NEW(str, len+1);
    for(i=0; i<len; i++){
        str[i]=buf[i];
    }
    str[len] = 0;
    return str;
}

//文字列が同じかどうかを判定する関数
int string_compare(String p, String q){
    int c1, c2;
    int i=0;
    while(1){
        c1=p[i]; c2=q[i];
        if(c1<c2) return -1;
        if(c1>c2) return 1;
        if(c1==0) break;
        i++;
    }
    return 0;
}

//新しい連結リストを作成
slist slist_new(void){
    slist L;
    NEW(L, 1);
    L -> head = NULL;
    L -> tail = NULL;
    return L;
}
//新しいリスト要素(つまり英和辞典における英語の見出しと対応する日本語のペア)
slobj slobj_new(String x, String y){
    slobj p;
    NEW(p, 1);
    p -> key = x;
    p -> jpn = y;
    p -> next = NULL;
    return p;
}

//連結リストの先頭に挿入
void slist_insert_head(slist L, slobj p){
    p -> next = L -> head;
    L -> head = p;
}

//連結リストの末尾に挿入
void slist_insert_tail(slist L, slobj p){
    if(L -> head == NULL){
        L -> tail = p;
        L -> head = p;
    }
    else if(L -> head == L -> tail){
        L -> tail = p;
        L -> head -> next = p;
    }
    else{
        L -> tail -> next = p;
        L -> tail = p;
    }
}

//連結リストをプリント
void slist_print(slist L)
{
    slobj p;
    p = L->head;
    while (p != NULL){
        if(string_compare(p->jpn, "NO")==0){
            printf("%s\n", p->jpn);
        }
        else{
            printf("%s %s\n", p -> key, p -> jpn);
        }
        p = p-> next;
    }
}

//表のサイズがmのハッシュ表を作る
hash hash_new(int m){
    hash H;
    int i;
    NEW(H.T, m);
    H.m = m;
    for(i=0; i<= m-1; i++){
        H.T[i]=slist_new();
    }
    return H;
}

//キーがkeyである要素を返す
slobj hash_search(hash H, String key){
    int h=hfunc(H, key);
    return H.T[h]->head;
}

void hash_insert(hash H, slobj obj){
    int h=hfunc(H, obj->key);
    slist_insert_tail(H.T[h], obj);
}

void slist_free(slist L){
    slobj p, q, r;
    p = L->head;
    q = p->next;
    while (q != NULL){
        r = q;
        q = q-> next;
        free(p);
        p = r;
    }
    free(p);
    free(L);
}

void hash_free(hash H){
    int i;
    for(i = 0; i <= H.m-1; i++){
        if(H.T[i] -> head != NULL){
            slist_free(H.T[i]);
        }
    }
    free(H.T);
}

int main(){
    int i, j, k, n;
    String eng, jpn, s;
    double v;
    slobj p, r;
    hash H;
    slist L=slist_new(); //ここに出力する実数を格納していく
    int m=81239; //数千から数万程度の素数がいいらしい
　　//ここから英和辞典を作成します。
    scanf("%d", &n); //英和辞典に記録していく英語日本語ペアの数
    H=hash_new(m);
    H.n = n;
　　//英語日本語ペアを順次入れていく
    for(i=1; i<=n; i++){
        eng=string_input();
        jpn=string_input();
        p=slobj_new(eng, jpn);
        hash_insert(H, p);
    }
　　//ここからはkeyを入力していきます。各keyに対応する英和辞典の見出しがある場合はそのkeyおよびそれに対応する日本語を、ない場合は-1と出力します
    scanf("%d", &k);//以後の問い合わせの数
    for(j=1; j<=k; j++){
        s=string_input();
        r=hash_search(H, s);
        if(r==NULL){
            r=slobj_new(NULL, "NO");
        }
        slist_insert_tail(L, r);
    }
    slist_print(L);
    slist_free(L);
    hash_free(H);
    return 0;
}
```

こちらのコードだと、例えば
```ここに言語を入力
4
coffee コーヒー
milk 牛乳
water 水
milkcoffee ミルクコーヒー
5
mizu
milk
coffe
milkcoffee
sake
```
のような比較的小さめなインプットだと正しい結果が出るのですが、それに対して
```ここに言語を入力
1021
hq め
meayl かヨはみカヘ
cvscxggb まねとそカらほ
fnf ンホろトこ
jprep うかフハホ
vy ンてうすぬのて
cqpev ム
ffmznim テヲちりロちコ
(中略)
992
jdysejw
hit
gqlakd
xxy
dburfwkbk
xwpw
aucltz
(中略)
```
のような長いインプットだと、間違ったkeyに対応する見出しが何個か出力されてしまい、正しく動作しないようです。

　自分で調べててみたところ、どうもハッシュ関数を改良したほうがよさそうなので、mの値を数万程度ではなく数百万程度の素数に変えるなどをしてみました。しかし、mにどのような値を入れてもうまくいきません。

　どこを改良するべきか、アドバイスいただけるでしょうか。宜しくお願いします。

編集：
衝突が起きる場合を想定して書き直しましたが、今度は同じスロットの要素を出力するときにおかしくなります。
```C
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

#define NEW(p, n){p = malloc((n)*sizeof(p[0]));}

typedef char* String;
//後々使いやすくするため、ここでStringタイプを定義しちゃいます

//英和辞書用のオブジェクトです(英語の見出しと日本語の意味のペア)
typedef struct slobj_{
    struct slobj_* next;
    String key;
    String jpn;
}* slobj;

//連結リスト
typedef struct{
    slobj head;
    slobj tail;
}* slist;

typedef struct{
    int n; //ハッシュに格納されている要素数
    int m; //ハッシュ表のサイズ
    slist* T; //リストの配列
} hash;

ハッシュ関数
int hfunc(hash H, String key){
    int h=0, i=0;
    while (key[i] != 0){
        h = h*3659+key[i]; //ハッシュ値を計算
        i++;
    }
    return abs(h) % H.m; //非負の値にして、表のサイズで割った余り
    //return 1; //ハッシュ関数が全て同じ値を出す場合で実験してみました。
}

//文字列の長さを求める
int string_len(String str){
    int len=0;
    while(str[len]!=0){
        len++;
    }
    return len;
}

//文字列を標準入力から読む
String string_input(void){
    int i, len;
    char buf[1000];
    String str;
    scanf("%999s", buf);

    len = string_len(buf);

    NEW(str, len+1);
    for(i=0; i<len; i++){
        str[i]=buf[i];
    }
    str[len] = 0;
    return str;
}

//文字列が同じかどうかを判定する関数
int string_compare(String p, String q){
    int c1, c2;
    int i=0;
    while(1){
        c1=p[i]; c2=q[i];
        if(c1<c2) return -1;
        if(c1>c2) return 1;
        if(c1==0) break;
        i++;
    }
    return 0;
}

//新しい連結リストを作成
slist slist_new(void){
    slist L;
    NEW(L, 1);
    L -> head = NULL;
    L -> tail = NULL;
    return L;
}

//新しいリスト要素(つまり英和辞典における英語の見出しと対応する日本語のペア)
slobj slobj_new(String x, String y){
    slobj p;
    NEW(p, 1);
    p -> key = x;
    p -> jpn = y;
    p -> next = NULL;
    return p;
}

//連結リストの先頭に挿入
void slist_insert_head(slist L, slobj p){
    p -> next = L -> head;
    L -> head = p;
}

//連結リストの末尾に挿入
void slist_insert_tail(slist L, slobj p){
    if(L -> head == NULL){
        L -> tail = p;
        L -> head = p;
    }
    else if(L -> head == L -> tail){
        L -> tail = p;
        L -> head -> next = p;
    }
    else{
        L -> tail -> next = p;
        L -> tail = p;
    }
}

//連結リストをプリント
void slist_print(slist L)
{
    slobj p;
    p = L->head;
    while (p != NULL){
        if(string_compare(p->jpn, "NO")==0){
            printf("%s\n", p->jpn);
        }
        else{
            printf("%s %s\n", p -> key, p -> jpn);
        }
        p = p-> next;
    }
}

//表のサイズがmのハッシュ表を作る
hash hash_new(int m){
    hash H;
    int i;
    NEW(H.T, m);
    H.m = m;
    for(i=0; i<= m-1; i++){
        H.T[i]=slist_new();
    }
    return H;
}

//キーがkeyである要素を返す
slobj hash_search(hash H, String key){
    slobj p;
    int h=hfunc(H, key);
    p = H.T[h]->head;
    while(p!=NULL){
        if(string_compare(p->key, key)==0){ //keyと一致するような要素を同じスロットにあるリストから探索していきます
           return p;
       }
        p = p->next;
       }
    return p;
}

//ハッシュに入力する関数。同じスロットにハッシュされたすべての要素が連結リストに格納されるようにします。
void hash_insert(hash H, slobj obj){
    int h=hfunc(H, obj->key);
    slist_insert_head(H.T[h], obj);
}

void slist_free(slist L){
    slobj p, q, r;
    p = L->head;
    q = p->next;
    while (q != NULL){
        r = q;
        q = q-> next;
        free(p);
        p = r;
    }
    free(p);
    free(L);
}

void hash_free(hash H){
    int i;
    for(i = 0; i <= H.m-1; i++){
        if(H.T[i] -> head != NULL){
            slist_free(H.T[i]);
        }
    }
    free(H.T);
}

int main(){
    int i, j, k, n;
    String eng, jpn, s;
    double v;
    slobj p, r;
    hash H;
    slist L=slist_new(); //ここに出力する実数を格納していく
    int m=81239; //数千から数万程度の素数がいいらしい
//ここから英和辞典を作成します。
    scanf("%d", &n); //英和辞典に記録していく英語日本語ペアの数
    H=hash_new(m);
    H.n = n;
//英語日本語ペアを順次入れていく
    for(i=1; i<=n; i++){
        eng=string_input();
        jpn=string_input();
        p=slobj_new(eng, jpn);
        hash_insert(H, p);
    }
//ここからはkeyを入力していきます。各keyに対応する英和辞典の見出しがある場合はそのkeyおよびそれに対応する日本語を、ない場合は-1と出力します
    scanf("%d", &k);//以後の問い合わせの数
    for(j=1; j<=k; j++){
        s=string_input();
        r=hash_search(H, s);
        if(r==NULL){
            r=slobj_new(NULL, "NO");
        }
        slist_insert_tail(L, r);
    }
    slist_print(L);
    //slist_free(L);
    //hash_free(H);
    return 0;
}
```
例えば、ハッシュ関数が常に1を出力するよう変更し、
```
3
coffee コーヒー
milk 牛乳
water 水
2
milk
coffee
```
という入力にした場合、
```
milk 牛乳
coffee コーヒー
milk 牛乳
coffee コーヒー
milk 牛乳
coffee コーヒー
・
・
・
```
が延々と続いてしまうのです！！！！！

編集2:
ごめんなさい、よく考えたらr=hash_search(H, s);→slist_insert_tail(L, r);のときは次のリストの要素を指すポインタもそのままコピーされるのですから、そりゃ無限ループになりますよね、、、

もう少し考えます

英和辞書を作成しているのですが、ハッシュ関数の選び方についてアドバイスを頂きたいです。

質問は１つです．
Entry<?,?>[] EMPTY_TABLEは，なぜEntry<K,V>[] EMPTY_TABLEではないのでしょうか．

java 1.7 のHashMap クラスのソースコードでは，EntryクラスのEnpty_talbleが以下のように宣言されています．
ここでジェネリクスの中身をワイルドカードにする理由はなにかあるのでしょうか．


/**
     * An empty table instance to share when the table is not inflated.
     */
    static final Entry<?,?>[] EMPTY_TABLE = {};

    /**
     * The table, resized as necessary. Length MUST Always be a power of two.
     */
    transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

なにか理由があるのであれば教えていただきたいです．
よろしくお願い致します．

Java 1.7のHashMap のtable の初期化についての質問です．

Java 1.7のHashMap に関しての質問です．質問は2つあります．
Rehashする際，どうやらsun.misc.VM.isBooted() というものを確認しているみたいです．
質問の一つ目は，このBootedをするとどのようなことがJava内で起こるか，ということです．
次の質問です．このVMがいつBootされるかに関して，
initializeSystemClass()が呼び出されている場合，Booted されるみたいです．
このinitialazeSystemClassとは，いつ呼び出されるのでしょうか．
質問が多く，申し訳ありません．よろしくお願い致します．

Java 1.7のHashMap に関しての質問です．

React初心者です

mapメソッドが定義されていないとのエラーなのですが、

taskが渡されていて、なぜマップメソッドが反応しないのかがわかりません、、、



```
TaskList.js

import React from 'react'
import {useSelector} from 'react-redux'
import {selectTasks} from './taskSlice'
import TaskItem from './TaskItem'

const TaskList = () => {
  const tasks = useSelector(selectTasks)
  return (
    <div>
      {tasks.map((task) => (
      <TaskItem key={task.id} task={task}/>
      ))}
    </div>
  )
}

export default TaskList
```

```
TaskItem.js

import React from 'react'
import {useDispatch} from 'react-redux'
import {completeTask, deleteTask} from "./taskSlice"

const TaskItem = ({task}) => {
  const dispatch = useDispatch()

  return (
    <div>
      <input type="checkbox"
      onClick = {() =>dispatch(completeTask(task))}
      defaultChecked={task.completed}
      />
      <span>{task.title}</span>
      <button onClick = {() =>dispatch(deleteTask(task))}>delete</button>
    </div>
  )
}

export default TaskItem

```

```
taskSlice.js

import { createSlice } from '@reduxjs/toolkit';

export const taskSlice = createSlice({
  name: 'task',
  initialState: {
    idCounter:{
      idCount: 3,
    },
    tasks: [
      {id: 1, title: 'TASK A',completed: false}, 
      {id: 2, title: 'TASK C',completed: false}, 
      {id: 3, title: 'TASK C',completed: false}, 
    ]
  },
  reducers: {
    newTask: (state, action) => {
      state.idCount  ++;
      const newItem ={
        id: state.idCount,
        title: action.payload,
        completed: false
      };
      state.tasks = [newItem ,...state.tasks];
    },

    completeTask: (state,action) => {
      const task = state.tasks.find((t) => t.di === action.payload.id)
      if(task){
        task.completed = !true.completed;
      }
    },
    deleteTask: (state,action) => {
      state.tasks += state.tasks.filter((t) =>t.id !== action.payload.id);
    },
  },
});

export const { newTask, completeTask, deleteTask } = taskSlice.actions;

export const selectTasks = (state) => state.task.tasks;

export default taskSlice.reducer;

```

× TypeError: tasks.map is not a function

次のコードを実行するとnullと表示されます。理由は大体想像がつくのですが、これで7と表示されるようにする(HashMapのキーの等価判定をequalsメソッドで行う)ためにはどうすればよいですか?

```Java
import java.util.*;

class Test{
  int a;
  boolean equals(Test other){
    if(this.a==other.a){
      return true;
    } else {
      return false;
    }
  }
  Test(int a){
    this.a=a;
  }
}

class Main {
  public static void main(String[] args) {
    HashMap<Test,Integer> a=new HashMap<Test,Integer>();
    a.put(new Test(5),7);
    System.out.println(a.get(new Test(5)));
  }
}
```

ハッシュマップ