java原理--Map 如何实现Key 的唯一性？
Map 如何实现Key 的唯一性？
在Map和Set不可存在重复元素？
1 对于 HashMap HashSet
他们的底层数据结构的实现是：维护了一张 HashTable 。容器中的元素全部存储在Hashtable 中。他们再添加元素的时候,是如何判断是否存在有重复元素的呢？ 每一个被添加的元素都有一个 hashCode(哈希值)，他们先比较哈希值，是否相同？ 不相同的元素，添加进入 HashTable. 如果hashCode相同的话， 再去比较 equals()方法，如果也相同的话，JVM就认为数据已经存在了，就不会添加数据！
代码说明
package stu.love.v;
import java.util.*;
//什么时候用Map
/*
当存在映射关系时，
每个学员都对应一个地址
姓名，年龄相同的视为同一个人
*/
// 容器中的对象 本身 具备比较性！
class StudentD implements Comparable<StudentD>
{
private String name;
private int age;
public StudentD(String name,int age)
{
this.name = name;
this.age = age;
}
public int compareTo(StudentD stu)
{
int t = this.age-stu.age;
return t==0?this.name.compareTo(stu.name):t;
}
// 重写了 hashCode 方法
public int hashCode()
{
return name.hashCode()+age*36;
}
// 重写了 equals 方法
public boolean equals(Object obj)
{
if(!(obj instanceof StudentD))
throw new ClassCastException("类型异常");
StudentD stu =(StudentD)obj;
return this.name.equals(stu.name) && this.age ==stu.age;
}
public void setName(String name)
{
this.name = name;
}
public void setAge(int age)
{
this.age = age;
}
public String getName()
{
return this.name;
}
public int getAge()
{
return this.age;
}
public String toString()
{
return this.name +","+age;
}
}
class Demo16
{
public static void main(String[] args)
{
//保证键唯一的原理，先判断哈希值是否相同，相同再判断equals()
HashMap<StudentD,String> hm = new HashMap<StudentD,String>();
hm.put(new StudentD("xiaobai",23),"shanghai");
hm.put(new StudentD("wanghei",20),"beijing");
hm.put(new StudentD("lisi",28),"shenzhen");
hm.put(new StudentD("lisi",28),"shenzhen");
// Map 第一种 迭代方式 根据 key 找 value
Set<StudentD> set=hm.keySet();
for(Iterator<StudentD> ite = set.iterator();ite.hasNext();)
{
StudentD stu = ite.next();
String value = hm.get(stu);
sop(stu+"的地址是:"+value);
}
// map 的 第二种 迭代方式 获取 键值对，entry 获取其中的 key 和 value
Set<Map.Entry<StudentD,String>> entry = hm.entrySet();
for(Iterator<Map.Entry<StudentD,String>> ite = entry.iterator();ite.hasNext();)
{
Map.Entry<StudentD,String> kv = ite.next();
StudentD key = kv.getKey();
String value = kv.getValue();
sop(key+"的地址是:"+value);
}
}
public static void sop(Object obj)
{
System.out.println(obj);
}
}2 对于 TreeMap TreeSet
他们底层是数据结构的实现是：维护了一棵二叉树。 容器中添加元素的时候，他们有是怎么判断是否有相同元素的？我们都直到 TreeMap TreeSet 她们 都是 有序的存储数据。 为了维护 数据的唯一性。 再存入数据的时候，他们会调用元素中 实现的 Comparable 的 compareTo() 方法（代码1）。 或者 集合本身创建的时候 传入了 迭代器（代码2）. 具体的实现是：调用比较方法，返回-1 的时候，添加到左子树，返回1 的时候 添加到 右子树。返回0 有相同数据 不添加该元素！
代码说明
package stu.love.v;
/*
TreeMap:
HashMap保证键唯一的原理和HashSet相同
TreeMap保证键唯一的原理和TreeSet相同
*/
import java.util.*;
class Student1
{
private String name;
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
private int age;
public Student1(String name,int age)
{
this.name = name;
this.age = age;
}
public String toString()
{
return name+","+age;
}
}
// 比较器
class CompareByName implements Comparator<Student1>
{
public int compare(Student1 s1,Student1 s2)
{
// 这样写的方法 非常好！ 简洁
int t = s1.getName().compareTo(s2.getName());
return t ==0?s1.getAge()-s2.getAge():t;
}
}
class Demo17
{
public static void main(String[] args)
{
// 原理二：
//保证键唯一的原理：比较方法的返回值为0
TreeMap<Student1,String> tm = new TreeMap<Student1,String>(new CompareByName());
tm.put(new Student1("xiaobai",23),"shanghai");
tm.put(new Student1("wanghei",20),"beijing");
tm.put(new Student1("lisi",28),"shenzhen");
tm.put(new Student1("lisi",28),"shenzhen");
Set<Map.Entry<Student1,String>> entry = tm.entrySet();
for(Iterator<Map.Entry<Student1,String>> it = entry.iterator();it.hasNext();)
{
Map.Entry<Student1,String> kv = it.next();
Student1 key = kv.getKey();
String value = kv.getValue();
sop(key+"的地址是:"+value);
}
}
public static void sop(Object obj)
{
System.out.println(obj);
}
}3如何做到Map中key唯一不重复，每次都遍历来equals比较吗？
答案是否。如果全部遍历的话，当Map中元素很多的时候，显然查询效率低。
HashMap属于散列存储结构，其table的存储是放在不同的Jvm内存区域。通过一个整型值来标识table的区域，相当于这个区域的下标。然后整个查找过程就从不再需要遍历整个table，只需遍历这一区域的数据即可。
结合HashMap.class中的put方法来说明：
如何找到这个区域呢？
1.首先将传入的key值用hash方法转化为int型的hash值，并且通过该方法让hash值变得各位更均匀一些。变得更均匀的目的是让每一个区域的大小更加等分些，公平利用存储空间，查询速度得到提升。
2.而后的indexfor方法将根据其hash值和table的大小得到这个区域的“位置下标”。具体其方法的实现同样也是为了让各个区域分布的更加均匀。
得到这个区域以后，再遍历这个区域来找到对应的元素
1.通过for循环遍历这个区域的链表，在循环中如果key值的hash值相等，并且其key值相等，那么进行覆盖原元素操作。
2.如果遍历结束依然没找到，则新添元素
参考https://blog.csdn.net/jiary5201314/article/details/51439982
查看5道真题和解析