HashSet的一个面试题

先定义一个Person类

public class Person {
	String name;
	int id;
	public Person(String name, int id) {
		super();
		this.name = name;
		this.id = id;
	}
	public Person() {
		super();
	}
	@Override
	public String toString() {
		return "Person [name=" + name + ", id=" + id + "]";
	}
	
	@Override
	public boolean equals(Object obj) {
		if(!(obj instanceof Person)) {
			return false;
		}
		Person p = (Person) obj;
		return this.id == p.id && this.name.equals(p.name);
	}
	@Override
	public int hashCode() {
		int result = 17;
		result = result * 37 + id;
		result = result * 37 + name.hashCode();
		return result;
	}
}

测试代码

import java.util.HashSet;
public class TestHashSet {
	public static void main(String[] args) {
		HashSet<Person> set = new HashSet<Person>();
		Person p1 = new Person("AA",1001);
		Person p2 = new Person("BB",1002);
		
		set.add(p1);
		set.add(p2);
		System.out.println(set);
		
		p1.name = "CC";//第一处
		set.remove(p1);// 第二处
		System.out.println(set);
		
		set.add(new Person("CC",1001));// 第三处
		System.out.println(set);
		set.add(new Person("AA",1001));// 第四处
		System.out.println(set);
	}
}

输出结果

[Person [name=AA, id=1001], Person [name=BB, id=1002]]
[Person [name=CC, id=1001], Person [name=BB, id=1002]]
[Person [name=CC, id=1001], Person [name=CC, id=1001], Person [name=BB, id=1002]]
[Person [name=CC, id=1001], Person [name=CC, id=1001], Person [name=AA, id=1001], Person [name=BB, id=1002]]

HashSet的底层是HashMap,数组加链表的方式实现，对象存储在堆中。 数组的长度为0-15，如何找到对应的位置，根据每个对象hashCode值计算出对应的数组位置：(注意此类有自定义的hashCode值的计算)

• 如果该位置没有元素，直接插入。
• 如果该位置上有元素，先比较HashCode值(HashCode值不一样计算出来的位置可能一样)
  • 如果hash值不一样，加进来形成链表
  • 如果hash值一样，再比较equals()
    • 为false，不一样。形成链表
    • 为true,重复元素，丢弃