从头认识java-15.7 Map（4）-介绍HashMap的工作原理-hash碰撞（常常作为面试题）

这一章节我们来讨论一下hash碰撞。

1.什么是hash碰撞？

就是两个对象的key的hashcode是一样的，这个时候怎么get他的value呢？

答案是通过equals遍历table那个位置上面的Entry链表。

2.样例

正常的样例：

package com.ray.ch14;

import java.util.HashMap;

public class Test {

	public static void main(String[] args) {

		HashMap<Person, Dog> map = new HashMap<Person, Dog>();

		Person person_1 = new Person();

		person_1.setHeight(180);

		person_1.setId(1);

		person_1.setName("person_1");

		Person person_2 = new Person();

		person_2.setHeight(180);

		person_2.setId(2);

		person_2.setName("person_1");

		Dog dog_1 = new Dog();

		dog_1.setId(1);

		dog_1.setName("dog_1");

		Dog dog_2 = new Dog();

		dog_2.setId(2);

		dog_2.setName("dog_2");

		map.put(person_1, dog_1);

		map.put(person_2, dog_2);

		System.out.println("--" + map.get(person_1).getName());

		System.out.println("--" + map.get(person_2).getName());

	}

}

class Dog {

	private int id = 0;

	private String name = "";

	public int getId() {

		return id;

	}

	public void setId(int id) {

		this.id = id;

	}

	public String getName() {

		return name;

	}

	public void setName(String name) {

		this.name = name;

	}

	@Override

	public int hashCode() {

		System.out.println("dog's hashCode() invoked");

		return id;

	}

	@Override

	public boolean equals(Object obj) {

		System.out.println("dog's equals invokes");

		return super.equals(obj);

	}

}

class Person {

	private int id = 0;

	private String name = "";

	private int height = 0;

	@Override

	public int hashCode() {

		System.out.println("person id:" + id + ",hashCode() invoked,"

				+ "hashcode:" + this.name.hashCode() + this.height);

		return super.hashCode();

	}

	public int getId() {

		return id;

	}

	public void setId(int id) {

		this.id = id;

	}

	public String getName() {

		return name;

	}

	public void setName(String name) {

		this.name = name;

	}

	public int getHeight() {

		return height;

	}

	public void setHeight(int height) {

		this.height = height;

	}

	@Override

	public String toString() {

		return "id:" + id + "; Name:" + this.name + "; height:" + this.height;

	}

	@Override

	public boolean equals(Object obj) {

		System.out.println("id:" + id + ", equals invokes");

		return super.equals(obj);

	}

}

输出：

person id:1,hashCode() invoked,hashcode:443164103180
person id:2,hashCode() invoked,hashcode:443164103180
person id:1,hashCode() invoked,hashcode:443164103180
--dog_1
person id:2,hashCode() invoked,hashcode:443164103180
--dog_2

解释：

（1）上面建立两个类。然后分别在hashCode和equal方法里面加上输出语句

（2）通过输出能够看到，事实上我们重写的equals方法是没有被调用的。我们仅仅须要通过hashcode就能够定位对应的对象

hash碰撞的代码：

package com.ray.ch14;

import java.util.HashMap;

public class Test {

	public static void main(String[] args) {

		HashMap<Person, Dog> map = new HashMap<Person, Dog>();

		Person person_1 = new Person();

		person_1.setHeight(180);

		person_1.setId(1);

		person_1.setName("person_1");

		Person person_2 = new Person();

		person_2.setHeight(180);

		person_2.setId(2);

		person_2.setName("person_1");

		Dog dog_1 = new Dog();

		dog_1.setId(1);

		dog_1.setName("dog_1");

		Dog dog_2 = new Dog();

		dog_2.setId(2);

		dog_2.setName("dog_2");

		map.put(person_1, dog_1);

		map.put(person_2, dog_2);

		System.out.println("--" + map.get(person_1).getName());

		System.out.println("--" + map.get(person_2).getName());

	}

}

class Dog {

	private int id = 0;

	private String name = "";

	public int getId() {

		return id;

	}

	public void setId(int id) {

		this.id = id;

	}

	public String getName() {

		return name;

	}

	public void setName(String name) {

		this.name = name;

	}

	@Override

	public int hashCode() {

		System.out.println("dog's hashCode() invoked");

		return id;

	}

	@Override

	public boolean equals(Object obj) {

		System.out.println("dog's equals invokes");

		return super.equals(obj);

	}

}

class Person {

	private int id = 0;

	private String name = "";

	private int height = 0;

	@Override

	public int hashCode() {

		System.out.println("person id:" + id + ",hashCode() invoked,"

				+ "hashcode:" + this.name.hashCode() + this.height);

		return this.name.hashCode() + this.height;// 重写的地方

	}

	public int getId() {

		return id;

	}

	public void setId(int id) {

		this.id = id;

	}

	public String getName() {

		return name;

	}

	public void setName(String name) {

		this.name = name;

	}

	public int getHeight() {

		return height;

	}

	public void setHeight(int height) {

		this.height = height;

	}

	@Override

	public String toString() {

		return "id:" + id + "; Name:" + this.name + "; height:" + this.height;

	}

	@Override

	public boolean equals(Object obj) {

		System.out.println("id:" + id + ", equals invokes");

		return super.equals(obj);

	}

}

输出：

person id:1,hashCode() invoked,hashcode:443164103180

person id:2,hashCode() invoked,hashcode:443164103180

id:2, equals invokes

person id:1,hashCode() invoked,hashcode:443164103180

id:1, equals invokes

--dog_1

person id:2,hashCode() invoked,hashcode:443164103180

--dog_2

解释：

（1）我们重写了Person。也就是key的hashCode方法。人为的产生hash碰撞现象

（2）从输出能够看出，上面的代码须要用到equals方法

回归put和get的源代码。

以下是put的源代码：

 public V put(K key, V value) {

        if (key == null)

            return putForNullKey(value);

        int hash = hash(key.hashCode());

        int i = indexFor(hash, table.length);

        for (Entry<K,V> e = table[i]; e != null; e = e.next) {

            Object k;

            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {//注意的地方

                V oldValue = e.value;

                e.value = value;

                e.recordAccess(this);

                return oldValue;

            }

        }

        modCount++;

        addEntry(hash, key, value, i);

        return null;

    }

以下是get的源代码：

public V get(Object key) {

        if (key == null)

            return getForNullKey();

        int hash = hash(key.hashCode());

        for (Entry<K,V> e = table[indexFor(hash, table.length)];

             e != null;

             e = e.next) {

            Object k;

            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))//注意的地方

                return e.value;

        }

        return null;

    }

大家请注意我上面凝视“注意的地方”：

（1）假设是寻常没有hash碰撞的时候，前面的两个hash比較再加上key的地址的比較就可以。然后后出现“短路”现象，使得后的句子不再运行。

（2）可是在出现hash碰撞的情况下。前面两个条件都成立，然后必须使用最后的equals来推断对象的相等。

3.hash碰撞出现的情景？

（1）通常会出如今大的数据情况之下

（2）hashcode的生成方法唯一性较弱（比方上面的人为的生产hashcode）

总结：这一章节主要通过介绍hash碰撞再一次深入了解HashMap的工作原理。

这一章节就到这里，谢谢。

-----------------------------------

文件夹

巴特西

从头认识java-15.7 Map（4）-介绍HashMap的工作原理-hash碰撞（常常作为面试题）

最新文章

热门文章