/
HashSearch.scala
57 lines (44 loc) · 1.23 KB
/
HashSearch.scala
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
package day15
/**
* Created by doctorq on 2017/6/30.
* 哈希查找
* 解决冲突的两种方法:链地址法,开放地址法
*/
object HashSearch extends App {
/**
* 直接定址法
*
* @param value
* @param length 常量
* @return
*/
def insertHash(array: Array[Int], value: Int, length: Int): Unit = {
var key = value % length
while (array(key) != 0) {
key = (key + 1) % length
}
array(key) = value
}
def searchHash(array: Array[Int], find: Int, length: Int): Int = {
var key = find % length
while (array(key) != 0 && array(key) != find) {
key = (key + 1) % length
}
if (array(key) == 0)
return -1
key
}
val length = 14
val arrayBuffer = new Array[Int](length)
val array = Array[Int](2, 4, 5, 63, 5, 6, 2, 3, 89, 34, 34, 7, 8)
array.foreach(item => insertHash(arrayBuffer, item, length))
// val hash = for (i <- 0 until length if (arrayBuffer(i) != 0)) yield arrayBuffer(i)
// hash.foreach(println)
arrayBuffer.foreach(println)
val find = 34
val hashKey = searchHash(arrayBuffer, find, length)
hashKey match {
case -1 => println(s"${find}' is not found")
case _ => println(s"${find}'s hashCode is ${hashKey}")
}
}