LinearHashTable

配列tのそれぞれの箱部分は「null(触っていない)」「値」「del（消された）」の3つの状態を持つ

table:linearhashtable

3 2 7 ／ 1

こんな感じ。ChainedHashTableのリストを横倒しした感じになる。空白になってるのがnullで、／がdel

テーブル帳は、値の個数とdelの個数の和q(つまりテーブル長 - nullの個数)の2倍以上のサイズになるようにする

その方が混みにくいので(実際、上の例ではlengthが17, q=4+1=5で、2倍しても10で満たしている)

Xを追加するときは「hash(X)に移動」->「nullが見つかるまで右に移動(端に行ったら先頭に戻る)」をする

Xを検索するときも、hash(X)に移動してから、nullかXが見つかるまで右に移動…をすればいい

nullは「まだ手をつけられていない」の意味なので、Xがnullより先に見つかることは絶対にない…ので、nullにぶつかった時は「ありませんでした」と言うことができる

Xを消すのは検索したやつをdelで置き換える感じ。