## 2020年6月15日月曜日

### Go - Go Packages, Algorithms, and Data Structures - hash table, key, module, map, linked list

Go Systems Programming: Master Linux and Unix system level programming with Go (Mihalis Tsoukalos(著)、Packt Publishing)のChapter 4(Go Packages, Algorithms, and Data Structures)、Exercises 7.の解答を求めてみる。

コード

```package main

import (
"fmt"
"math/rand"
"time"
)

type node struct {
value int
next  *node
}
type hashTable struct {
table map[int]*node
size  int
}

func hashFunction(i, size int) int {
return i % size
}
func exist(hash *hashTable, index, value int) bool {
for n := hash.table[index]; n != nil; n = n.next {
if n.value == value {
return true
}
}
return false
}
func insert(hash *hashTable, value int) int {
index := hashFunction(value, hash.size)
if exist(hash, index, value) {
return -1
}
element := node{value: value, next: hash.table[index]}
hash.table[index] = &element
return index
}
func traverse(hash *hashTable) {
for k := range hash.table {
if hash.table[k] != nil {
for t := hash.table[k]; t != nil; t = t.next {
fmt.Printf("%d -> ", t.value)
}
fmt.Println()
}
}
}
func main() {
rand.Seed(time.Now().UnixNano())
table := make(map[int]*node, 10)
hash := &hashTable{table: table, size: 10}
fmt.Println("Number of spaces:", hash.size)
for i := 0; i < 95; i++ {
n := rand.Intn(95)
fmt.Printf("insert(%v)\n", n)
if insert(hash, n) != -1 {
traverse(hash)
}
}
}
```

```% go build hash.go
% ./hash
Number of spaces: 10
insert(12)
12 ->
insert(73)
12 ->
73 ->
insert(63)
12 ->
63 -> 73 ->
insert(80)
80 ->
63 -> 73 ->
12 ->
insert(43)
12 ->
43 -> 63 -> 73 ->
80 ->
insert(72)
80 ->
43 -> 63 -> 73 ->
72 -> 12 ->
insert(49)
72 -> 12 ->
43 -> 63 -> 73 ->
49 ->
80 ->
insert(93)
49 ->
72 -> 12 ->
93 -> 43 -> 63 -> 73 ->
80 ->
insert(57)
80 ->
57 ->
72 -> 12 ->
93 -> 43 -> 63 -> 73 ->
49 ->
insert(34)
72 -> 12 ->
93 -> 43 -> 63 -> 73 ->
49 ->
34 ->
80 ->
57 ->
insert(75)
80 ->
57 ->
75 ->
34 ->
72 -> 12 ->
93 -> 43 -> 63 -> 73 ->
49 ->
insert(3)
34 ->
72 -> 12 ->
3 -> 93 -> 43 -> 63 -> 73 ->
49 ->
80 ->
57 ->
75 ->
insert(21)
72 -> 12 ->
3 -> 93 -> 43 -> 63 -> 73 ->
49 ->
34 ->
80 ->
57 ->
75 ->
21 ->
insert(54)
80 ->
57 ->
75 ->
21 ->
72 -> 12 ->
3 -> 93 -> 43 -> 63 -> 73 ->
49 ->
54 -> 34 ->
insert(45)
3 -> 93 -> 43 -> 63 -> 73 ->
49 ->
54 -> 34 ->
72 -> 12 ->
57 ->
45 -> 75 ->
21 ->
80 ->
insert(74)
21 ->
80 ->
57 ->
45 -> 75 ->
74 -> 54 -> 34 ->
72 -> 12 ->
3 -> 93 -> 43 -> 63 -> 73 ->
49 ->
insert(76)
72 -> 12 ->
3 -> 93 -> 43 -> 63 -> 73 ->
49 ->
74 -> 54 -> 34 ->
76 ->
80 ->
57 ->
45 -> 75 ->
21 ->
insert(80)
insert(33)
72 -> 12 ->
33 -> 3 -> 93 -> 43 -> 63 -> 73 ->
49 ->
74 -> 54 -> 34 ->
76 ->
80 ->
57 ->
45 -> 75 ->
21 ->
insert(15)
80 ->
57 ->
15 -> 45 -> 75 ->
21 ->
72 -> 12 ->
33 -> 3 -> 93 -> 43 -> 63 -> 73 ->
49 ->
74 -> 54 -> 34 ->
76 ->
insert(55)
80 ->
57 ->
55 -> 15 -> 45 -> 75 ->
21 ->
72 -> 12 ->
33 -> 3 -> 93 -> 43 -> 63 -> 73 ->
49 ->
74 -> 54 -> 34 ->
76 ->
insert(22)
22 -> 72 -> 12 ->
33 -> 3 -> 93 -> 43 -> 63 -> 73 ->
49 ->
74 -> 54 -> 34 ->
76 ->
80 ->
57 ->
55 -> 15 -> 45 -> 75 ->
21 ->
insert(75)
insert(27)
80 ->
27 -> 57 ->
55 -> 15 -> 45 -> 75 ->
21 ->
76 ->
22 -> 72 -> 12 ->
33 -> 3 -> 93 -> 43 -> 63 -> 73 ->
49 ->
74 -> 54 -> 34 ->
insert(68)
80 ->
27 -> 57 ->
55 -> 15 -> 45 -> 75 ->
21 ->
68 ->
22 -> 72 -> 12 ->
33 -> 3 -> 93 -> 43 -> 63 -> 73 ->
49 ->
74 -> 54 -> 34 ->
76 ->
insert(61)
49 ->
74 -> 54 -> 34 ->
76 ->
22 -> 72 -> 12 ->
33 -> 3 -> 93 -> 43 -> 63 -> 73 ->
55 -> 15 -> 45 -> 75 ->
61 -> 21 ->
68 ->
80 ->
27 -> 57 ->
insert(3)
insert(13)
80 ->
27 -> 57 ->
55 -> 15 -> 45 -> 75 ->
61 -> 21 ->
68 ->
22 -> 72 -> 12 ->
13 -> 33 -> 3 -> 93 -> 43 -> 63 -> 73 ->
49 ->
74 -> 54 -> 34 ->
76 ->
insert(31)
22 -> 72 -> 12 ->
13 -> 33 -> 3 -> 93 -> 43 -> 63 -> 73 ->
49 ->
74 -> 54 -> 34 ->
76 ->
80 ->
27 -> 57 ->
55 -> 15 -> 45 -> 75 ->
31 -> 61 -> 21 ->
68 ->
insert(73)
insert(43)
insert(39)
13 -> 33 -> 3 -> 93 -> 43 -> 63 -> 73 ->
39 -> 49 ->
74 -> 54 -> 34 ->
76 ->
22 -> 72 -> 12 ->
27 -> 57 ->
55 -> 15 -> 45 -> 75 ->
31 -> 61 -> 21 ->
68 ->
80 ->
insert(91)
80 ->
27 -> 57 ->
55 -> 15 -> 45 -> 75 ->
91 -> 31 -> 61 -> 21 ->
68 ->
22 -> 72 -> 12 ->
13 -> 33 -> 3 -> 93 -> 43 -> 63 -> 73 ->
39 -> 49 ->
74 -> 54 -> 34 ->
76 ->
insert(68)
insert(6)
68 ->
80 ->
27 -> 57 ->
55 -> 15 -> 45 -> 75 ->
91 -> 31 -> 61 -> 21 ->
6 -> 76 ->
22 -> 72 -> 12 ->
13 -> 33 -> 3 -> 93 -> 43 -> 63 -> 73 ->
39 -> 49 ->
74 -> 54 -> 34 ->
insert(71)
13 -> 33 -> 3 -> 93 -> 43 -> 63 -> 73 ->
39 -> 49 ->
74 -> 54 -> 34 ->
6 -> 76 ->
22 -> 72 -> 12 ->
27 -> 57 ->
55 -> 15 -> 45 -> 75 ->
71 -> 91 -> 31 -> 61 -> 21 ->
68 ->
80 ->
insert(61)
insert(78)
78 -> 68 ->
80 ->
27 -> 57 ->
55 -> 15 -> 45 -> 75 ->
71 -> 91 -> 31 -> 61 -> 21 ->
6 -> 76 ->
22 -> 72 -> 12 ->
13 -> 33 -> 3 -> 93 -> 43 -> 63 -> 73 ->
39 -> 49 ->
74 -> 54 -> 34 ->
insert(58)
6 -> 76 ->
22 -> 72 -> 12 ->
13 -> 33 -> 3 -> 93 -> 43 -> 63 -> 73 ->
39 -> 49 ->
74 -> 54 -> 34 ->
58 -> 78 -> 68 ->
80 ->
27 -> 57 ->
55 -> 15 -> 45 -> 75 ->
71 -> 91 -> 31 -> 61 -> 21 ->
insert(56)
55 -> 15 -> 45 -> 75 ->
71 -> 91 -> 31 -> 61 -> 21 ->
58 -> 78 -> 68 ->
80 ->
27 -> 57 ->
39 -> 49 ->
74 -> 54 -> 34 ->
56 -> 6 -> 76 ->
22 -> 72 -> 12 ->
13 -> 33 -> 3 -> 93 -> 43 -> 63 -> 73 ->
insert(45)
insert(19)
80 ->
27 -> 57 ->
55 -> 15 -> 45 -> 75 ->
71 -> 91 -> 31 -> 61 -> 21 ->
58 -> 78 -> 68 ->
22 -> 72 -> 12 ->
13 -> 33 -> 3 -> 93 -> 43 -> 63 -> 73 ->
19 -> 39 -> 49 ->
74 -> 54 -> 34 ->
56 -> 6 -> 76 ->
insert(26)
80 ->
27 -> 57 ->
55 -> 15 -> 45 -> 75 ->
71 -> 91 -> 31 -> 61 -> 21 ->
58 -> 78 -> 68 ->
22 -> 72 -> 12 ->
13 -> 33 -> 3 -> 93 -> 43 -> 63 -> 73 ->
19 -> 39 -> 49 ->
74 -> 54 -> 34 ->
26 -> 56 -> 6 -> 76 ->
insert(81)
22 -> 72 -> 12 ->
13 -> 33 -> 3 -> 93 -> 43 -> 63 -> 73 ->
19 -> 39 -> 49 ->
74 -> 54 -> 34 ->
26 -> 56 -> 6 -> 76 ->
80 ->
27 -> 57 ->
55 -> 15 -> 45 -> 75 ->
81 -> 71 -> 91 -> 31 -> 61 -> 21 ->
58 -> 78 -> 68 ->
insert(54)
insert(75)
insert(55)
insert(14)
22 -> 72 -> 12 ->
13 -> 33 -> 3 -> 93 -> 43 -> 63 -> 73 ->
19 -> 39 -> 49 ->
14 -> 74 -> 54 -> 34 ->
26 -> 56 -> 6 -> 76 ->
80 ->
27 -> 57 ->
55 -> 15 -> 45 -> 75 ->
81 -> 71 -> 91 -> 31 -> 61 -> 21 ->
58 -> 78 -> 68 ->
insert(42)
19 -> 39 -> 49 ->
14 -> 74 -> 54 -> 34 ->
26 -> 56 -> 6 -> 76 ->
42 -> 22 -> 72 -> 12 ->
13 -> 33 -> 3 -> 93 -> 43 -> 63 -> 73 ->
55 -> 15 -> 45 -> 75 ->
81 -> 71 -> 91 -> 31 -> 61 -> 21 ->
58 -> 78 -> 68 ->
80 ->
27 -> 57 ->
insert(46)
42 -> 22 -> 72 -> 12 ->
13 -> 33 -> 3 -> 93 -> 43 -> 63 -> 73 ->
19 -> 39 -> 49 ->
14 -> 74 -> 54 -> 34 ->
46 -> 26 -> 56 -> 6 -> 76 ->
80 ->
27 -> 57 ->
55 -> 15 -> 45 -> 75 ->
81 -> 71 -> 91 -> 31 -> 61 -> 21 ->
58 -> 78 -> 68 ->
insert(60)
19 -> 39 -> 49 ->
14 -> 74 -> 54 -> 34 ->
46 -> 26 -> 56 -> 6 -> 76 ->
42 -> 22 -> 72 -> 12 ->
13 -> 33 -> 3 -> 93 -> 43 -> 63 -> 73 ->
55 -> 15 -> 45 -> 75 ->
81 -> 71 -> 91 -> 31 -> 61 -> 21 ->
58 -> 78 -> 68 ->
60 -> 80 ->
27 -> 57 ->
insert(2)
58 -> 78 -> 68 ->
60 -> 80 ->
27 -> 57 ->
55 -> 15 -> 45 -> 75 ->
81 -> 71 -> 91 -> 31 -> 61 -> 21 ->
46 -> 26 -> 56 -> 6 -> 76 ->
2 -> 42 -> 22 -> 72 -> 12 ->
13 -> 33 -> 3 -> 93 -> 43 -> 63 -> 73 ->
19 -> 39 -> 49 ->
14 -> 74 -> 54 -> 34 ->
insert(35)
27 -> 57 ->
35 -> 55 -> 15 -> 45 -> 75 ->
81 -> 71 -> 91 -> 31 -> 61 -> 21 ->
58 -> 78 -> 68 ->
60 -> 80 ->
13 -> 33 -> 3 -> 93 -> 43 -> 63 -> 73 ->
19 -> 39 -> 49 ->
14 -> 74 -> 54 -> 34 ->
46 -> 26 -> 56 -> 6 -> 76 ->
2 -> 42 -> 22 -> 72 -> 12 ->
insert(29)
27 -> 57 ->
35 -> 55 -> 15 -> 45 -> 75 ->
81 -> 71 -> 91 -> 31 -> 61 -> 21 ->
58 -> 78 -> 68 ->
60 -> 80 ->
13 -> 33 -> 3 -> 93 -> 43 -> 63 -> 73 ->
29 -> 19 -> 39 -> 49 ->
14 -> 74 -> 54 -> 34 ->
46 -> 26 -> 56 -> 6 -> 76 ->
2 -> 42 -> 22 -> 72 -> 12 ->
insert(60)
insert(19)
insert(43)
insert(11)
58 -> 78 -> 68 ->
60 -> 80 ->
27 -> 57 ->
35 -> 55 -> 15 -> 45 -> 75 ->
11 -> 81 -> 71 -> 91 -> 31 -> 61 -> 21 ->
46 -> 26 -> 56 -> 6 -> 76 ->
2 -> 42 -> 22 -> 72 -> 12 ->
13 -> 33 -> 3 -> 93 -> 43 -> 63 -> 73 ->
29 -> 19 -> 39 -> 49 ->
14 -> 74 -> 54 -> 34 ->
insert(88)
2 -> 42 -> 22 -> 72 -> 12 ->
13 -> 33 -> 3 -> 93 -> 43 -> 63 -> 73 ->
29 -> 19 -> 39 -> 49 ->
14 -> 74 -> 54 -> 34 ->
46 -> 26 -> 56 -> 6 -> 76 ->
60 -> 80 ->
27 -> 57 ->
35 -> 55 -> 15 -> 45 -> 75 ->
11 -> 81 -> 71 -> 91 -> 31 -> 61 -> 21 ->
88 -> 58 -> 78 -> 68 ->
insert(20)
35 -> 55 -> 15 -> 45 -> 75 ->
11 -> 81 -> 71 -> 91 -> 31 -> 61 -> 21 ->
88 -> 58 -> 78 -> 68 ->
20 -> 60 -> 80 ->
27 -> 57 ->
29 -> 19 -> 39 -> 49 ->
14 -> 74 -> 54 -> 34 ->
46 -> 26 -> 56 -> 6 -> 76 ->
2 -> 42 -> 22 -> 72 -> 12 ->
13 -> 33 -> 3 -> 93 -> 43 -> 63 -> 73 ->
insert(4)
35 -> 55 -> 15 -> 45 -> 75 ->
11 -> 81 -> 71 -> 91 -> 31 -> 61 -> 21 ->
88 -> 58 -> 78 -> 68 ->
20 -> 60 -> 80 ->
27 -> 57 ->
29 -> 19 -> 39 -> 49 ->
4 -> 14 -> 74 -> 54 -> 34 ->
46 -> 26 -> 56 -> 6 -> 76 ->
2 -> 42 -> 22 -> 72 -> 12 ->
13 -> 33 -> 3 -> 93 -> 43 -> 63 -> 73 ->
insert(51)
27 -> 57 ->
35 -> 55 -> 15 -> 45 -> 75 ->
51 -> 11 -> 81 -> 71 -> 91 -> 31 -> 61 -> 21 ->
88 -> 58 -> 78 -> 68 ->
20 -> 60 -> 80 ->
13 -> 33 -> 3 -> 93 -> 43 -> 63 -> 73 ->
29 -> 19 -> 39 -> 49 ->
4 -> 14 -> 74 -> 54 -> 34 ->
46 -> 26 -> 56 -> 6 -> 76 ->
2 -> 42 -> 22 -> 72 -> 12 ->
insert(40)
40 -> 20 -> 60 -> 80 ->
27 -> 57 ->
35 -> 55 -> 15 -> 45 -> 75 ->
51 -> 11 -> 81 -> 71 -> 91 -> 31 -> 61 -> 21 ->
88 -> 58 -> 78 -> 68 ->
2 -> 42 -> 22 -> 72 -> 12 ->
13 -> 33 -> 3 -> 93 -> 43 -> 63 -> 73 ->
29 -> 19 -> 39 -> 49 ->
4 -> 14 -> 74 -> 54 -> 34 ->
46 -> 26 -> 56 -> 6 -> 76 ->
insert(6)
insert(47)
47 -> 27 -> 57 ->
35 -> 55 -> 15 -> 45 -> 75 ->
51 -> 11 -> 81 -> 71 -> 91 -> 31 -> 61 -> 21 ->
88 -> 58 -> 78 -> 68 ->
40 -> 20 -> 60 -> 80 ->
13 -> 33 -> 3 -> 93 -> 43 -> 63 -> 73 ->
29 -> 19 -> 39 -> 49 ->
4 -> 14 -> 74 -> 54 -> 34 ->
46 -> 26 -> 56 -> 6 -> 76 ->
2 -> 42 -> 22 -> 72 -> 12 ->
insert(14)
insert(91)
insert(83)
40 -> 20 -> 60 -> 80 ->
47 -> 27 -> 57 ->
35 -> 55 -> 15 -> 45 -> 75 ->
51 -> 11 -> 81 -> 71 -> 91 -> 31 -> 61 -> 21 ->
88 -> 58 -> 78 -> 68 ->
2 -> 42 -> 22 -> 72 -> 12 ->
83 -> 13 -> 33 -> 3 -> 93 -> 43 -> 63 -> 73 ->
29 -> 19 -> 39 -> 49 ->
4 -> 14 -> 74 -> 54 -> 34 ->
46 -> 26 -> 56 -> 6 -> 76 ->
insert(72)
insert(72)
insert(50)
88 -> 58 -> 78 -> 68 ->
50 -> 40 -> 20 -> 60 -> 80 ->
47 -> 27 -> 57 ->
35 -> 55 -> 15 -> 45 -> 75 ->
51 -> 11 -> 81 -> 71 -> 91 -> 31 -> 61 -> 21 ->
46 -> 26 -> 56 -> 6 -> 76 ->
2 -> 42 -> 22 -> 72 -> 12 ->
83 -> 13 -> 33 -> 3 -> 93 -> 43 -> 63 -> 73 ->
29 -> 19 -> 39 -> 49 ->
4 -> 14 -> 74 -> 54 -> 34 ->
insert(1)
4 -> 14 -> 74 -> 54 -> 34 ->
46 -> 26 -> 56 -> 6 -> 76 ->
2 -> 42 -> 22 -> 72 -> 12 ->
83 -> 13 -> 33 -> 3 -> 93 -> 43 -> 63 -> 73 ->
29 -> 19 -> 39 -> 49 ->
1 -> 51 -> 11 -> 81 -> 71 -> 91 -> 31 -> 61 -> 21 ->
88 -> 58 -> 78 -> 68 ->
50 -> 40 -> 20 -> 60 -> 80 ->
47 -> 27 -> 57 ->
35 -> 55 -> 15 -> 45 -> 75 ->
insert(71)
insert(22)
insert(61)
insert(77)
88 -> 58 -> 78 -> 68 ->
50 -> 40 -> 20 -> 60 -> 80 ->
77 -> 47 -> 27 -> 57 ->
35 -> 55 -> 15 -> 45 -> 75 ->
1 -> 51 -> 11 -> 81 -> 71 -> 91 -> 31 -> 61 -> 21 ->
46 -> 26 -> 56 -> 6 -> 76 ->
2 -> 42 -> 22 -> 72 -> 12 ->
83 -> 13 -> 33 -> 3 -> 93 -> 43 -> 63 -> 73 ->
29 -> 19 -> 39 -> 49 ->
4 -> 14 -> 74 -> 54 -> 34 ->
insert(79)
2 -> 42 -> 22 -> 72 -> 12 ->
83 -> 13 -> 33 -> 3 -> 93 -> 43 -> 63 -> 73 ->
79 -> 29 -> 19 -> 39 -> 49 ->
4 -> 14 -> 74 -> 54 -> 34 ->
46 -> 26 -> 56 -> 6 -> 76 ->
50 -> 40 -> 20 -> 60 -> 80 ->
77 -> 47 -> 27 -> 57 ->
35 -> 55 -> 15 -> 45 -> 75 ->
1 -> 51 -> 11 -> 81 -> 71 -> 91 -> 31 -> 61 -> 21 ->
88 -> 58 -> 78 -> 68 ->
insert(14)
insert(11)
insert(63)
insert(48)
2 -> 42 -> 22 -> 72 -> 12 ->
83 -> 13 -> 33 -> 3 -> 93 -> 43 -> 63 -> 73 ->
79 -> 29 -> 19 -> 39 -> 49 ->
4 -> 14 -> 74 -> 54 -> 34 ->
46 -> 26 -> 56 -> 6 -> 76 ->
50 -> 40 -> 20 -> 60 -> 80 ->
77 -> 47 -> 27 -> 57 ->
35 -> 55 -> 15 -> 45 -> 75 ->
1 -> 51 -> 11 -> 81 -> 71 -> 91 -> 31 -> 61 -> 21 ->
48 -> 88 -> 58 -> 78 -> 68 ->
insert(51)
insert(11)
insert(90)
77 -> 47 -> 27 -> 57 ->
35 -> 55 -> 15 -> 45 -> 75 ->
1 -> 51 -> 11 -> 81 -> 71 -> 91 -> 31 -> 61 -> 21 ->
48 -> 88 -> 58 -> 78 -> 68 ->
90 -> 50 -> 40 -> 20 -> 60 -> 80 ->
83 -> 13 -> 33 -> 3 -> 93 -> 43 -> 63 -> 73 ->
79 -> 29 -> 19 -> 39 -> 49 ->
4 -> 14 -> 74 -> 54 -> 34 ->
46 -> 26 -> 56 -> 6 -> 76 ->
2 -> 42 -> 22 -> 72 -> 12 ->
insert(90)
insert(11)
insert(64)
2 -> 42 -> 22 -> 72 -> 12 ->
83 -> 13 -> 33 -> 3 -> 93 -> 43 -> 63 -> 73 ->
79 -> 29 -> 19 -> 39 -> 49 ->
64 -> 4 -> 14 -> 74 -> 54 -> 34 ->
46 -> 26 -> 56 -> 6 -> 76 ->
90 -> 50 -> 40 -> 20 -> 60 -> 80 ->
77 -> 47 -> 27 -> 57 ->
35 -> 55 -> 15 -> 45 -> 75 ->
1 -> 51 -> 11 -> 81 -> 71 -> 91 -> 31 -> 61 -> 21 ->
48 -> 88 -> 58 -> 78 -> 68 ->
insert(15)
insert(76)
insert(29)
insert(87)
2 -> 42 -> 22 -> 72 -> 12 ->
83 -> 13 -> 33 -> 3 -> 93 -> 43 -> 63 -> 73 ->
79 -> 29 -> 19 -> 39 -> 49 ->
64 -> 4 -> 14 -> 74 -> 54 -> 34 ->
46 -> 26 -> 56 -> 6 -> 76 ->
90 -> 50 -> 40 -> 20 -> 60 -> 80 ->
87 -> 77 -> 47 -> 27 -> 57 ->
35 -> 55 -> 15 -> 45 -> 75 ->
1 -> 51 -> 11 -> 81 -> 71 -> 91 -> 31 -> 61 -> 21 ->
48 -> 88 -> 58 -> 78 -> 68 ->
insert(12)
insert(86)
83 -> 13 -> 33 -> 3 -> 93 -> 43 -> 63 -> 73 ->
79 -> 29 -> 19 -> 39 -> 49 ->
64 -> 4 -> 14 -> 74 -> 54 -> 34 ->
86 -> 46 -> 26 -> 56 -> 6 -> 76 ->
2 -> 42 -> 22 -> 72 -> 12 ->
87 -> 77 -> 47 -> 27 -> 57 ->
35 -> 55 -> 15 -> 45 -> 75 ->
1 -> 51 -> 11 -> 81 -> 71 -> 91 -> 31 -> 61 -> 21 ->
48 -> 88 -> 58 -> 78 -> 68 ->
90 -> 50 -> 40 -> 20 -> 60 -> 80 ->
insert(16)
2 -> 42 -> 22 -> 72 -> 12 ->
83 -> 13 -> 33 -> 3 -> 93 -> 43 -> 63 -> 73 ->
79 -> 29 -> 19 -> 39 -> 49 ->
64 -> 4 -> 14 -> 74 -> 54 -> 34 ->
16 -> 86 -> 46 -> 26 -> 56 -> 6 -> 76 ->
90 -> 50 -> 40 -> 20 -> 60 -> 80 ->
87 -> 77 -> 47 -> 27 -> 57 ->
35 -> 55 -> 15 -> 45 -> 75 ->
1 -> 51 -> 11 -> 81 -> 71 -> 91 -> 31 -> 61 -> 21 ->
48 -> 88 -> 58 -> 78 -> 68 ->
insert(47)
% ./hash
Number of spaces: 10
insert(90)
90 ->
insert(36)
36 ->
90 ->
insert(73)
36 ->
73 ->
90 ->
insert(2)
90 ->
36 ->
73 ->
2 ->
insert(34)
90 ->
36 ->
73 ->
34 ->
2 ->
insert(63)
2 ->
90 ->
36 ->
63 -> 73 ->
34 ->
insert(46)
2 ->
34 ->
90 ->
46 -> 36 ->
63 -> 73 ->
insert(9)
2 ->
9 ->
90 ->
46 -> 36 ->
63 -> 73 ->
34 ->
insert(45)
45 ->
2 ->
9 ->
63 -> 73 ->
34 ->
90 ->
46 -> 36 ->
insert(83)
83 -> 63 -> 73 ->
34 ->
90 ->
46 -> 36 ->
45 ->
2 ->
9 ->
insert(29)
2 ->
29 -> 9 ->
45 ->
90 ->
46 -> 36 ->
83 -> 63 -> 73 ->
34 ->
insert(13)
2 ->
29 -> 9 ->
45 ->
90 ->
46 -> 36 ->
13 -> 83 -> 63 -> 73 ->
34 ->
insert(69)
2 ->
69 -> 29 -> 9 ->
45 ->
90 ->
46 -> 36 ->
13 -> 83 -> 63 -> 73 ->
34 ->
insert(36)
insert(51)
34 ->
90 ->
46 -> 36 ->
13 -> 83 -> 63 -> 73 ->
51 ->
2 ->
69 -> 29 -> 9 ->
45 ->
insert(8)
90 ->
46 -> 36 ->
13 -> 83 -> 63 -> 73 ->
34 ->
8 ->
2 ->
69 -> 29 -> 9 ->
45 ->
51 ->
insert(69)
insert(35)
46 -> 36 ->
13 -> 83 -> 63 -> 73 ->
34 ->
8 ->
90 ->
69 -> 29 -> 9 ->
35 -> 45 ->
51 ->
2 ->
insert(8)
insert(89)
13 -> 83 -> 63 -> 73 ->
34 ->
8 ->
90 ->
46 -> 36 ->
35 -> 45 ->
51 ->
2 ->
89 -> 69 -> 29 -> 9 ->
insert(54)
51 ->
2 ->
89 -> 69 -> 29 -> 9 ->
35 -> 45 ->
54 -> 34 ->
8 ->
90 ->
46 -> 36 ->
13 -> 83 -> 63 -> 73 ->
insert(30)
30 -> 90 ->
46 -> 36 ->
13 -> 83 -> 63 -> 73 ->
54 -> 34 ->
8 ->
2 ->
89 -> 69 -> 29 -> 9 ->
35 -> 45 ->
51 ->
insert(31)
2 ->
89 -> 69 -> 29 -> 9 ->
35 -> 45 ->
31 -> 51 ->
30 -> 90 ->
46 -> 36 ->
13 -> 83 -> 63 -> 73 ->
54 -> 34 ->
8 ->
insert(42)
46 -> 36 ->
13 -> 83 -> 63 -> 73 ->
54 -> 34 ->
8 ->
30 -> 90 ->
89 -> 69 -> 29 -> 9 ->
35 -> 45 ->
31 -> 51 ->
42 -> 2 ->
insert(14)
30 -> 90 ->
46 -> 36 ->
13 -> 83 -> 63 -> 73 ->
14 -> 54 -> 34 ->
8 ->
42 -> 2 ->
89 -> 69 -> 29 -> 9 ->
35 -> 45 ->
31 -> 51 ->
insert(80)
42 -> 2 ->
89 -> 69 -> 29 -> 9 ->
35 -> 45 ->
31 -> 51 ->
80 -> 30 -> 90 ->
46 -> 36 ->
13 -> 83 -> 63 -> 73 ->
14 -> 54 -> 34 ->
8 ->
insert(14)
insert(31)
insert(61)
13 -> 83 -> 63 -> 73 ->
14 -> 54 -> 34 ->
8 ->
80 -> 30 -> 90 ->
46 -> 36 ->
35 -> 45 ->
61 -> 31 -> 51 ->
42 -> 2 ->
89 -> 69 -> 29 -> 9 ->
insert(50)
35 -> 45 ->
61 -> 31 -> 51 ->
42 -> 2 ->
89 -> 69 -> 29 -> 9 ->
13 -> 83 -> 63 -> 73 ->
14 -> 54 -> 34 ->
8 ->
50 -> 80 -> 30 -> 90 ->
46 -> 36 ->
insert(31)
insert(11)
42 -> 2 ->
89 -> 69 -> 29 -> 9 ->
35 -> 45 ->
11 -> 61 -> 31 -> 51 ->
8 ->
50 -> 80 -> 30 -> 90 ->
46 -> 36 ->
13 -> 83 -> 63 -> 73 ->
14 -> 54 -> 34 ->
insert(6)
50 -> 80 -> 30 -> 90 ->
6 -> 46 -> 36 ->
13 -> 83 -> 63 -> 73 ->
14 -> 54 -> 34 ->
8 ->
42 -> 2 ->
89 -> 69 -> 29 -> 9 ->
35 -> 45 ->
11 -> 61 -> 31 -> 51 ->
insert(52)
52 -> 42 -> 2 ->
89 -> 69 -> 29 -> 9 ->
35 -> 45 ->
11 -> 61 -> 31 -> 51 ->
50 -> 80 -> 30 -> 90 ->
6 -> 46 -> 36 ->
13 -> 83 -> 63 -> 73 ->
14 -> 54 -> 34 ->
8 ->
insert(80)
insert(66)
52 -> 42 -> 2 ->
89 -> 69 -> 29 -> 9 ->
35 -> 45 ->
11 -> 61 -> 31 -> 51 ->
50 -> 80 -> 30 -> 90 ->
66 -> 6 -> 46 -> 36 ->
13 -> 83 -> 63 -> 73 ->
14 -> 54 -> 34 ->
8 ->
insert(40)
52 -> 42 -> 2 ->
89 -> 69 -> 29 -> 9 ->
35 -> 45 ->
11 -> 61 -> 31 -> 51 ->
40 -> 50 -> 80 -> 30 -> 90 ->
66 -> 6 -> 46 -> 36 ->
13 -> 83 -> 63 -> 73 ->
14 -> 54 -> 34 ->
8 ->
insert(43)
11 -> 61 -> 31 -> 51 ->
52 -> 42 -> 2 ->
89 -> 69 -> 29 -> 9 ->
35 -> 45 ->
14 -> 54 -> 34 ->
8 ->
40 -> 50 -> 80 -> 30 -> 90 ->
66 -> 6 -> 46 -> 36 ->
43 -> 13 -> 83 -> 63 -> 73 ->
insert(65)
66 -> 6 -> 46 -> 36 ->
43 -> 13 -> 83 -> 63 -> 73 ->
14 -> 54 -> 34 ->
8 ->
40 -> 50 -> 80 -> 30 -> 90 ->
89 -> 69 -> 29 -> 9 ->
65 -> 35 -> 45 ->
11 -> 61 -> 31 -> 51 ->
52 -> 42 -> 2 ->
insert(10)
8 ->
10 -> 40 -> 50 -> 80 -> 30 -> 90 ->
66 -> 6 -> 46 -> 36 ->
43 -> 13 -> 83 -> 63 -> 73 ->
14 -> 54 -> 34 ->
52 -> 42 -> 2 ->
89 -> 69 -> 29 -> 9 ->
65 -> 35 -> 45 ->
11 -> 61 -> 31 -> 51 ->
insert(70)
8 ->
70 -> 10 -> 40 -> 50 -> 80 -> 30 -> 90 ->
66 -> 6 -> 46 -> 36 ->
43 -> 13 -> 83 -> 63 -> 73 ->
14 -> 54 -> 34 ->
52 -> 42 -> 2 ->
89 -> 69 -> 29 -> 9 ->
65 -> 35 -> 45 ->
11 -> 61 -> 31 -> 51 ->
insert(54)
insert(88)
52 -> 42 -> 2 ->
89 -> 69 -> 29 -> 9 ->
65 -> 35 -> 45 ->
11 -> 61 -> 31 -> 51 ->
70 -> 10 -> 40 -> 50 -> 80 -> 30 -> 90 ->
66 -> 6 -> 46 -> 36 ->
43 -> 13 -> 83 -> 63 -> 73 ->
14 -> 54 -> 34 ->
88 -> 8 ->
insert(3)
52 -> 42 -> 2 ->
89 -> 69 -> 29 -> 9 ->
65 -> 35 -> 45 ->
11 -> 61 -> 31 -> 51 ->
88 -> 8 ->
70 -> 10 -> 40 -> 50 -> 80 -> 30 -> 90 ->
66 -> 6 -> 46 -> 36 ->
3 -> 43 -> 13 -> 83 -> 63 -> 73 ->
14 -> 54 -> 34 ->
insert(37)
89 -> 69 -> 29 -> 9 ->
65 -> 35 -> 45 ->
11 -> 61 -> 31 -> 51 ->
52 -> 42 -> 2 ->
66 -> 6 -> 46 -> 36 ->
3 -> 43 -> 13 -> 83 -> 63 -> 73 ->
14 -> 54 -> 34 ->
88 -> 8 ->
37 ->
70 -> 10 -> 40 -> 50 -> 80 -> 30 -> 90 ->
insert(46)
insert(34)
insert(24)
3 -> 43 -> 13 -> 83 -> 63 -> 73 ->
24 -> 14 -> 54 -> 34 ->
88 -> 8 ->
37 ->
70 -> 10 -> 40 -> 50 -> 80 -> 30 -> 90 ->
66 -> 6 -> 46 -> 36 ->
65 -> 35 -> 45 ->
11 -> 61 -> 31 -> 51 ->
52 -> 42 -> 2 ->
89 -> 69 -> 29 -> 9 ->
insert(50)
insert(1)
66 -> 6 -> 46 -> 36 ->
3 -> 43 -> 13 -> 83 -> 63 -> 73 ->
24 -> 14 -> 54 -> 34 ->
88 -> 8 ->
37 ->
70 -> 10 -> 40 -> 50 -> 80 -> 30 -> 90 ->
89 -> 69 -> 29 -> 9 ->
65 -> 35 -> 45 ->
1 -> 11 -> 61 -> 31 -> 51 ->
52 -> 42 -> 2 ->
insert(67)
88 -> 8 ->
67 -> 37 ->
70 -> 10 -> 40 -> 50 -> 80 -> 30 -> 90 ->
66 -> 6 -> 46 -> 36 ->
3 -> 43 -> 13 -> 83 -> 63 -> 73 ->
24 -> 14 -> 54 -> 34 ->
52 -> 42 -> 2 ->
89 -> 69 -> 29 -> 9 ->
65 -> 35 -> 45 ->
1 -> 11 -> 61 -> 31 -> 51 ->
insert(34)
insert(25)
25 -> 65 -> 35 -> 45 ->
1 -> 11 -> 61 -> 31 -> 51 ->
52 -> 42 -> 2 ->
89 -> 69 -> 29 -> 9 ->
3 -> 43 -> 13 -> 83 -> 63 -> 73 ->
24 -> 14 -> 54 -> 34 ->
88 -> 8 ->
67 -> 37 ->
70 -> 10 -> 40 -> 50 -> 80 -> 30 -> 90 ->
66 -> 6 -> 46 -> 36 ->
insert(91)
70 -> 10 -> 40 -> 50 -> 80 -> 30 -> 90 ->
66 -> 6 -> 46 -> 36 ->
3 -> 43 -> 13 -> 83 -> 63 -> 73 ->
24 -> 14 -> 54 -> 34 ->
88 -> 8 ->
67 -> 37 ->
52 -> 42 -> 2 ->
89 -> 69 -> 29 -> 9 ->
25 -> 65 -> 35 -> 45 ->
91 -> 1 -> 11 -> 61 -> 31 -> 51 ->
insert(1)
insert(8)
insert(49)
52 -> 42 -> 2 ->
49 -> 89 -> 69 -> 29 -> 9 ->
25 -> 65 -> 35 -> 45 ->
91 -> 1 -> 11 -> 61 -> 31 -> 51 ->
70 -> 10 -> 40 -> 50 -> 80 -> 30 -> 90 ->
66 -> 6 -> 46 -> 36 ->
3 -> 43 -> 13 -> 83 -> 63 -> 73 ->
24 -> 14 -> 54 -> 34 ->
88 -> 8 ->
67 -> 37 ->
insert(73)
insert(0)
52 -> 42 -> 2 ->
49 -> 89 -> 69 -> 29 -> 9 ->
25 -> 65 -> 35 -> 45 ->
91 -> 1 -> 11 -> 61 -> 31 -> 51 ->
67 -> 37 ->
0 -> 70 -> 10 -> 40 -> 50 -> 80 -> 30 -> 90 ->
66 -> 6 -> 46 -> 36 ->
3 -> 43 -> 13 -> 83 -> 63 -> 73 ->
24 -> 14 -> 54 -> 34 ->
88 -> 8 ->
insert(39)
52 -> 42 -> 2 ->
39 -> 49 -> 89 -> 69 -> 29 -> 9 ->
25 -> 65 -> 35 -> 45 ->
91 -> 1 -> 11 -> 61 -> 31 -> 51 ->
0 -> 70 -> 10 -> 40 -> 50 -> 80 -> 30 -> 90 ->
66 -> 6 -> 46 -> 36 ->
3 -> 43 -> 13 -> 83 -> 63 -> 73 ->
24 -> 14 -> 54 -> 34 ->
88 -> 8 ->
67 -> 37 ->
insert(90)
insert(8)
insert(47)
3 -> 43 -> 13 -> 83 -> 63 -> 73 ->
24 -> 14 -> 54 -> 34 ->
88 -> 8 ->
47 -> 67 -> 37 ->
0 -> 70 -> 10 -> 40 -> 50 -> 80 -> 30 -> 90 ->
66 -> 6 -> 46 -> 36 ->
25 -> 65 -> 35 -> 45 ->
91 -> 1 -> 11 -> 61 -> 31 -> 51 ->
52 -> 42 -> 2 ->
39 -> 49 -> 89 -> 69 -> 29 -> 9 ->
insert(35)
insert(5)
52 -> 42 -> 2 ->
39 -> 49 -> 89 -> 69 -> 29 -> 9 ->
5 -> 25 -> 65 -> 35 -> 45 ->
91 -> 1 -> 11 -> 61 -> 31 -> 51 ->
0 -> 70 -> 10 -> 40 -> 50 -> 80 -> 30 -> 90 ->
66 -> 6 -> 46 -> 36 ->
3 -> 43 -> 13 -> 83 -> 63 -> 73 ->
24 -> 14 -> 54 -> 34 ->
88 -> 8 ->
47 -> 67 -> 37 ->
insert(50)
insert(44)
52 -> 42 -> 2 ->
39 -> 49 -> 89 -> 69 -> 29 -> 9 ->
5 -> 25 -> 65 -> 35 -> 45 ->
91 -> 1 -> 11 -> 61 -> 31 -> 51 ->
47 -> 67 -> 37 ->
0 -> 70 -> 10 -> 40 -> 50 -> 80 -> 30 -> 90 ->
66 -> 6 -> 46 -> 36 ->
3 -> 43 -> 13 -> 83 -> 63 -> 73 ->
44 -> 24 -> 14 -> 54 -> 34 ->
88 -> 8 ->
insert(49)
insert(46)
insert(40)
insert(12)
88 -> 8 ->
47 -> 67 -> 37 ->
0 -> 70 -> 10 -> 40 -> 50 -> 80 -> 30 -> 90 ->
66 -> 6 -> 46 -> 36 ->
3 -> 43 -> 13 -> 83 -> 63 -> 73 ->
44 -> 24 -> 14 -> 54 -> 34 ->
12 -> 52 -> 42 -> 2 ->
39 -> 49 -> 89 -> 69 -> 29 -> 9 ->
5 -> 25 -> 65 -> 35 -> 45 ->
91 -> 1 -> 11 -> 61 -> 31 -> 51 ->
insert(64)
12 -> 52 -> 42 -> 2 ->
39 -> 49 -> 89 -> 69 -> 29 -> 9 ->
5 -> 25 -> 65 -> 35 -> 45 ->
91 -> 1 -> 11 -> 61 -> 31 -> 51 ->
0 -> 70 -> 10 -> 40 -> 50 -> 80 -> 30 -> 90 ->
66 -> 6 -> 46 -> 36 ->
3 -> 43 -> 13 -> 83 -> 63 -> 73 ->
64 -> 44 -> 24 -> 14 -> 54 -> 34 ->
88 -> 8 ->
47 -> 67 -> 37 ->
insert(21)
12 -> 52 -> 42 -> 2 ->
39 -> 49 -> 89 -> 69 -> 29 -> 9 ->
5 -> 25 -> 65 -> 35 -> 45 ->
21 -> 91 -> 1 -> 11 -> 61 -> 31 -> 51 ->
47 -> 67 -> 37 ->
0 -> 70 -> 10 -> 40 -> 50 -> 80 -> 30 -> 90 ->
66 -> 6 -> 46 -> 36 ->
3 -> 43 -> 13 -> 83 -> 63 -> 73 ->
64 -> 44 -> 24 -> 14 -> 54 -> 34 ->
88 -> 8 ->
insert(1)
insert(34)
insert(77)
12 -> 52 -> 42 -> 2 ->
39 -> 49 -> 89 -> 69 -> 29 -> 9 ->
5 -> 25 -> 65 -> 35 -> 45 ->
21 -> 91 -> 1 -> 11 -> 61 -> 31 -> 51 ->
88 -> 8 ->
77 -> 47 -> 67 -> 37 ->
0 -> 70 -> 10 -> 40 -> 50 -> 80 -> 30 -> 90 ->
66 -> 6 -> 46 -> 36 ->
3 -> 43 -> 13 -> 83 -> 63 -> 73 ->
64 -> 44 -> 24 -> 14 -> 54 -> 34 ->
insert(26)
12 -> 52 -> 42 -> 2 ->
39 -> 49 -> 89 -> 69 -> 29 -> 9 ->
5 -> 25 -> 65 -> 35 -> 45 ->
21 -> 91 -> 1 -> 11 -> 61 -> 31 -> 51 ->
77 -> 47 -> 67 -> 37 ->
0 -> 70 -> 10 -> 40 -> 50 -> 80 -> 30 -> 90 ->
26 -> 66 -> 6 -> 46 -> 36 ->
3 -> 43 -> 13 -> 83 -> 63 -> 73 ->
64 -> 44 -> 24 -> 14 -> 54 -> 34 ->
88 -> 8 ->
insert(12)
insert(11)
insert(51)
insert(52)
insert(41)
12 -> 52 -> 42 -> 2 ->
39 -> 49 -> 89 -> 69 -> 29 -> 9 ->
5 -> 25 -> 65 -> 35 -> 45 ->
41 -> 21 -> 91 -> 1 -> 11 -> 61 -> 31 -> 51 ->
88 -> 8 ->
77 -> 47 -> 67 -> 37 ->
0 -> 70 -> 10 -> 40 -> 50 -> 80 -> 30 -> 90 ->
26 -> 66 -> 6 -> 46 -> 36 ->
3 -> 43 -> 13 -> 83 -> 63 -> 73 ->
64 -> 44 -> 24 -> 14 -> 54 -> 34 ->
insert(77)
insert(6)
insert(42)
insert(8)
insert(81)
26 -> 66 -> 6 -> 46 -> 36 ->
3 -> 43 -> 13 -> 83 -> 63 -> 73 ->
64 -> 44 -> 24 -> 14 -> 54 -> 34 ->
88 -> 8 ->
77 -> 47 -> 67 -> 37 ->
0 -> 70 -> 10 -> 40 -> 50 -> 80 -> 30 -> 90 ->
39 -> 49 -> 89 -> 69 -> 29 -> 9 ->
5 -> 25 -> 65 -> 35 -> 45 ->
81 -> 41 -> 21 -> 91 -> 1 -> 11 -> 61 -> 31 -> 51 ->
12 -> 52 -> 42 -> 2 ->
insert(38)
81 -> 41 -> 21 -> 91 -> 1 -> 11 -> 61 -> 31 -> 51 ->
12 -> 52 -> 42 -> 2 ->
39 -> 49 -> 89 -> 69 -> 29 -> 9 ->
5 -> 25 -> 65 -> 35 -> 45 ->
64 -> 44 -> 24 -> 14 -> 54 -> 34 ->
38 -> 88 -> 8 ->
77 -> 47 -> 67 -> 37 ->
0 -> 70 -> 10 -> 40 -> 50 -> 80 -> 30 -> 90 ->
26 -> 66 -> 6 -> 46 -> 36 ->
3 -> 43 -> 13 -> 83 -> 63 -> 73 ->
insert(72)
72 -> 12 -> 52 -> 42 -> 2 ->
39 -> 49 -> 89 -> 69 -> 29 -> 9 ->
5 -> 25 -> 65 -> 35 -> 45 ->
81 -> 41 -> 21 -> 91 -> 1 -> 11 -> 61 -> 31 -> 51 ->
0 -> 70 -> 10 -> 40 -> 50 -> 80 -> 30 -> 90 ->
26 -> 66 -> 6 -> 46 -> 36 ->
3 -> 43 -> 13 -> 83 -> 63 -> 73 ->
64 -> 44 -> 24 -> 14 -> 54 -> 34 ->
38 -> 88 -> 8 ->
77 -> 47 -> 67 -> 37 ->
insert(4)
72 -> 12 -> 52 -> 42 -> 2 ->
39 -> 49 -> 89 -> 69 -> 29 -> 9 ->
5 -> 25 -> 65 -> 35 -> 45 ->
81 -> 41 -> 21 -> 91 -> 1 -> 11 -> 61 -> 31 -> 51 ->
0 -> 70 -> 10 -> 40 -> 50 -> 80 -> 30 -> 90 ->
26 -> 66 -> 6 -> 46 -> 36 ->
3 -> 43 -> 13 -> 83 -> 63 -> 73 ->
4 -> 64 -> 44 -> 24 -> 14 -> 54 -> 34 ->
38 -> 88 -> 8 ->
77 -> 47 -> 67 -> 37 ->
insert(47)
insert(0)
insert(45)
insert(11)
insert(21)
%
```