1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
structure Hashtable :> HASHTABLE = struct
(* (Array, (cells occupied, total size)) *)
type 'a t = ((string * 'a) option) array * (int * int)
exception HashtableFull
exception Exists
fun create size = (Array.array (size, NONE), (0, size))
val fillLimit = 0.75
val ` = Word32.fromInt
fun hashFunc key =
let
open Word32
in
List.foldl (fn (x, acc) => acc * `31 + `(ord x)) (`0) $ explode key
end
fun insert (buf, (taken, total)) key value =
if Real.fromInt (taken + 1) / Real.fromInt total > fillLimit then
raise HashtableFull
else
let
open Array
val hash = hashFunc key
(* TODO: use bitwise manipulation instead of mod *)
val i = ref $ Word32.toInt $ Word32.mod (hash, `(length buf))
val flag = ref true
in
while !flag do (
case sub (buf, !i) of
NONE => (update (buf, !i, SOME (key, value)); flag := false)
| SOME (key', _) =>
if key' = key then
raise Exists
else
i := (!i + 1) mod (length buf)
)
end
fun lookup (buf, _) key =
let
open Array
val hash = hashFunc key
val i = ref $ Word32.toInt $ Word32.mod (hash, `(length buf))
val flag = ref true
val result = ref NONE
in
while !flag do (
case sub (buf, !i) of
SOME (key', value) =>
if key' = key then
(result := SOME value; flag := false)
else
i := (!i + 1) mod (length buf)
| NONE => flag := false
);
!result
end
end
|
