|
说到哈希我们很容易想到HashMap和HashSet，其中HashSet封装的就是HashMap，HashMap的原理很简单，就是数组加链表的形式。如果有做Android开发的，可能比较熟悉，Android中有个类ArrayMap，他就是以纯数组的形式进行存储的，其中Hash值是排序的，相同的Hash值会挨着，存放数据的数组是hash数组的两倍，因为存放数据的key和value是成对出现的，查找的时候先找到hash值的位置，然后在数据数组中相对应位置2倍的地方进行查找，如果没有再往前或往后找，这个原理很简单。hash查找首先要构造hash值，hash值的构造方式非常多，什么平均取中法，折叠法，平方法，求模法，等等等……。然后就是碰撞问题，HashMap解决碰撞问题是以链表的形式存在，ArrayMap出现碰撞时以数组的形式存在，并且出现碰撞都会挨着的。我们这里来写一个简单的查找，严格意义上来说不能说是查找，因为他不能确定要查找的元素在原数组中发位置，只能确定有没有，我们这里解决碰撞和上面两种都不一样，是以数组形式但是不挨着。 1public static void main(String args[]) {
2 int array[] = {2, 8, 3, 7, 1, 21, 36, 17};
3 int hashLength = 30;
4 int hash[] = new int[hashLength];
5 for (int i = 0; i < array.length; i++) {
6 insertHash(hash, array[i]);
7 }
8 for (int i = 0; i < 50; i++) {
9 int index = searchHash(hash, hashLength, i);
10 if (index != -1)
11 System.out.println("原数组中有" + i + "这个元素");
12 }
13}
14
15public static int searchHash(int[] hash, int hashLength, int key) {
16 int index = key % hashLength;
17 while (hash[index] != 0 && hash[index] != key) {
18 index = (++index) % hashLength;
19 }
20 if (hash[index] == 0)
21 return -1;
22 return index;
23}
24
25public static void insertHash(int[] hash, int data) {
26 int index = data % hash.length;
27 while (hash[index] != 0) {
28 index = (++index) % hash.length;
29 }
30 hash[index] = data;
31}
这里hashLength的长度不能小于原数组的长度，否则会出现死循环。其中searchHash函数返回的是数据在hash数组中存放的下标，不是原数组的下标。当然上面代码也有缺点，就是原数组中不能包含0，因为hash数组没赋初值，默认值也是0，所以解决方式就是给hash数组中每一个元素都赋一个原数组中不可能出现的初值，比如Integer.MIN_VALUE。下面我们来看下运行结果
|
