ОФП 4 лаба Хэш Таблица

 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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
class keyvalue[K, V](val key: K, val value: V)
class hashtable[K, V>:Null] private (val array: List[List[keyvalue[K,V]]]) {
def this() = this(Nil);
private def hfunc(key: K) : Int = {
key.hashCode() % 100;
}
def list(key: K) : List[keyvalue[K,V]] = {
array(hfunc(key))
}
private def existkey2( key: K, list: List[keyvalue[K, V]]) : Boolean = (list, key) match {
case (Nil, key) => false
case (x :: xs, key) if (x.key == key) => true
case (x :: xs, key) => existkey2(key, xs)
}
def existkey(key: K) : Boolean = array match {
case Nil => false
case _ if(existkey2(key, list(key))) => true
case _ => false
}
private def getvalue2(key: K, list: List[keyvalue[K, V]]) : V = (list, key) match {
case (Nil, key) => null
case (x :: xs, key) if (x.key == key) => x.value
case (x :: xs, key) => getvalue2(key, xs)
}
def getvalue(key: K) : V = {
if (!existkey(key)) null
else getvalue2(key, list(key))
}
private def init(key: K, value: V, i: Int) : List[List[keyvalue[K,V]]] = {
if (i < 100) {
if (hfunc(key) == i) {
val pair = new keyvalue[K, V](key, value);
val list: List[keyvalue[K, V]] = pair :: Nil;
list :: init(key, value, i+1)
} else Nil :: init(key, value, i+1)
} else Nil
}
private def insert2(key: K, value: V, i: Int) : List[List[keyvalue[K,V]]] = {
if (i < 100) {
if (hfunc(key) == i) {
val pair = new keyvalue[K, V](key, value);
val oldlist: List[keyvalue[K, V]] = list(key);
val newlist: List[keyvalue[K, V]] = pair :: oldlist;
newlist :: insert2(key, value, i+1);
} else array(i) :: insert2(key, value, i+1);
} else Nil;
}
def insert(key: K, value: V) : hashtable[K, V] = {
if (array == Nil) new hashtable[K, V](init(key, value, 0))
else if (existkey(key)) this
else new hashtable[K, V](insert2(key, value, 0))
}
private def delete3(key: K, oldlist: List[keyvalue[K, V]]) : List[keyvalue[K, V]] = (key, oldlist) match {
case (key, Nil) => Nil
case (key, x :: xs) if (x.key == key) => delete3(key, xs)
case (key, x :: xs) => x :: delete3(key, xs)
}
private def delete2(key: K, i: Int) : List[List[keyvalue[K,V]]] = {
if (i < 100) {
if (hfunc(key) == i) {
val newlist: List[keyvalue[K, V]] = delete3(key, list(key));
newlist :: delete2(key, i+1);
} else array(i) :: delete2(key, i+1);
} else Nil;
}
def delete(key: K) : hashtable[K, V] = {
if (array == Nil) this
else if (existkey(key)) new hashtable[K, V] (delete2(key, 0))
else this
}
}
val a = new hashtable[Int, String]
val b = a.insert(5,"asd")
val b2 = b.insert(8, "ewr")
val b3 = b2.insert(7, "ftp")
val b1 = b3.delete(5)
val c = b1.getvalue(5)
val c1 = b1.getvalue(7)
val e = b1.existkey(5)
val f = b1.existkey(8)
val h = b1.existkey(9)
val b4 = b3.insert(107, "1tp")
val b5 = b4.list(7)