Java中实现hash算法
Hash
  Hash，⼀般翻译做“散列”，也有直接⾳译为“哈希”的，就是把任意长度的输⼊，通过散列算法，变换成固定长度的输出，该输出就是散列值。根据散列值作为地址存放数据，这种转换是⼀种压缩映射，简单的说就是⼀种将任意长度的消息压缩到某⼀固定长度的消息摘要的函数。查关键字数据（如K）的时候，若结构中存在和关键字相等的记录，则必定在f(K)的存储位置上。由此，不需⽐较便可直接取得所查记录。我们称这个对应关系f为散列函数(Hash function)，按这个事件建⽴的表为散列表。
  综上所述，根据散列函数f(key)和处理冲突的⽅法将⼀组关键字映象到⼀个有限的连续的地址集（区间）上，并以关键字在地址集中
的“象” 作为记录在表中的存储位置，这种表便称为散列表，这⼀映象过程称为散列造表或散列，所得的存储位置称散列地址。
Hash冲突　
  对不同的关键字可能得到同⼀散列地址，即key1≠key2，⽽f(key1)=f(key2)，这种现象称hash冲突。即：key1通过f(key1)得到散列地址去存储key1，同理，key2发现⾃⼰对应的散列地址已经被key1占据了。
解决办法（总共有四种）：
1.开放寻址法
  所谓的开放定址法就是⼀旦发⽣了冲突，就去寻下⼀个空的散列地址，只要散列表⾜够⼤，空的散列地址总能到，并将记录存⼊。
  开放寻址法：Hi=(H(key) + di) MOD m,i=1,2,…，k(k<=m-1)，其中H(key)为散列函数，m为散列表长，di为增量序列，可有下列三种取法：
    1)． di=1,2,3,…，m-1，称线性探测再散列；
    2)． di=1^2,(-1)^2,2^2,(-2)^2,(3)^2,…，±(k)^2,(k<=m/2)称⼆次探测再散列；
    3)． di=伪随机数序列，称伪随机探测再散列。
  ⽤开放定址法解决冲突的做法是：当冲突发⽣时，使⽤某种探测技术（线性探测法、⼆次探测法（解决线性探测的堆积问题）、随机探测法（和⼆次探测原理⼀致，不⼀样的是：⼆次探测以定值跳跃，⽽随机探测的散列地址跳跃长度是不定值））在散列表中形成⼀个探测序列。沿此序列逐个单元地查，直到到给定的关键字，或者碰到⼀个开放的地址（即该地址单元为空）为⽌插⼊即可。
  ⽐如说，我们的关键字集合为{12,67,56,16,25,37,22,29,15,47,48,34}，表长为12。我们⽤散列函数f(key) = key mod l2
  当计算前S个数{12,67,56,16,25}时，都是没有冲突的散列地址，直接存⼊：
  计算key = 37时，发现f(37) = 1，此时就与25所在的位置冲突。
  于是我们应⽤上⾯的公式f(37) = (f(37)+1) mod 12 = 2。于是将37存⼊下标为2的位置：
2.再哈希
  再哈希法⼜叫双哈希法，有多个不同的Hash函数，当发⽣冲突时，使⽤第⼆个，第三个，….，等哈希函数去计算地址，直到⽆冲突。虽然不易发⽣聚集，但是增加了计算时间。
3.链地址法(Java hashmap就是这么做的)
  链地址法的基本思想是：每个哈希表节点都有⼀个next指针，多个哈希表节点可以⽤next指针构成⼀个单向链表，将所有关键字为同义词的结点链接在同⼀个单链表中，如：
  设有 m ＝ 5 ， H(K) ＝ K mod 5 ，关键字值序例 5 ， 21 ， 17 ， 9 ， 15 ， 36 ， 41 ， 24 ，按外链地址法所建⽴的哈希表如下图所
⽰：
4.建⽴⼀个公共溢出区
  这种⽅法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发⽣冲突的元素，⼀律填⼊溢出表。代码实现：
  Person类：
    关于Java中的hashCode⽅法，详情请见：
1package my.hash;
2
3/**
4 * Person类
5 * 重写hashCode⽅法和equals⽅法
6 * hashCode⽅法计算该对象的散列码
7 * Java中每个对象都有⼀个散列码
8 * @author ASUS
9 *
10*/
11
12public class Person {
13private String name;
14private int age;
15
16//set和get⽅法
17public String getName() {
18return name;
19    }
20public void setName(String name) {
21this.name = name;
22    }
23public int getAge() {
24return age;
25    }
26public void setAge(int age) {
27this.age = age;
28    }
29
30//构造器
31public Person(String name,int age){
32super();
33this.age=age;
34this.name=name;
35    }
36
37//输出⽅法
38public String toString() {
39return "Person [name="+name+",age="+age+"]";
40    }
41
42//重写hashcode⽅法
43public int hashCode() {
44final int prime=31;
45int result=1;
46        result=prime*result+age;
47        result=prime*result+((name==null)?0:name.hashCode());
48return result;
49    }
50
51/*重写equals⽅法
52    * 重写该⽅法时必须重写hashCode⽅法，因为要确保⼀个对象映射到同⼀个存储地址
53*/
54public boolean equals(Object object) {
55if(this==object){
56return true;
57        }
冒泡排序java代码详解58if(object==null){
59return false;
60        }
61if(getClass()!=Class()){
62return false;
63        }
64        Person other=(Person)object;
65if(age!=other.age){
66if(other.name!=null){
67return false;
68            }
69        }else if (!name.equals(other.name)) {
70return false;
71        }
72return true;
73    }
74 }
  关于该Java代码中的getClass⽅法，详情请见：
  测试类：
1package my.hash;
2
3import java.util.HashSet;
4
5public class Test {
6public static void main(String[] args) {
7//构造6个person对象
8        Person p1=new Person("sam", 10);
9        Person p2=new Person("amy", 13);
10        Person p3=new Person("lili", 22);
11        Person p4=new Person("daming", 34);
12        Person p5=new Person("a", 2);
13        Person p6=new Person("b", 2);
14
15//输出a和b的hashcode值
16        System.out.println("a的hashcode值："+p5.hashCode()+"  b的hashcode值："+p6.hashCode());
17
18//定义⼀个HashSet，将Person对象存储在该集合中
19        HashSet<Person> set=new HashSet<Person>();
20
21//将Person对象添加进HashSet集合中
22        set.add(p6);
23        set.add(p5);
24        set.add(p4);
25        set.add(p3);
26        set.add(p2);
27        set.add(p1);
28
29//遍历HashSet，若p5和p6的hashCode⼀致，但是却添加进了集合set，说明hashset底层解决了hash冲突的问题。30for(Person person :set){
31            System.out.println(person);
32        }
33    }
34 }
  运⾏结果：

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。