Ⅰ java 关于集合Set接口的实现类中 元素相等的问题
HashSet确实是靠hashcode来运算出这个元素应该存放在什么地方。
但是不同的对象，hashcode也可能会相同。
这时就发生了冲突，需要再次比较发生冲突的两个或多个元素是否相同（通过equals方法）。
如果相同添加失败，如果不同添加成功。
为什么不直接用equals比较是否相同？
因为不知道该跟哪个元素比较啊，难不成遍历整个Set来比较？
如果有一万个元素呢，那么将会很费时间。
而先算出hashcode在比较有个好处。
只要hashcode不同，则可以确定元素不同。只有hashcode相同的情况下，元素才有可能相同。
hashcode的性质：
如果两个元素相同，那么其hashcode必定相同。
如果两个元素不同，那么不要求其hashcode一定不同。（但是如果不同的元素尽量能返回不同的hashcode，那么将有助于提高HashSet的性能）
Ⅱ 深入浅出的分析 Set集合
Set集合的特点主要有：元素不重复、存储无序的特点。
打开 Set 集合，主要实现类有 HashSet、LinkedHashSet 、TreeSet 、EnumSet（ RegularEnumSet、JumboEnumSet ）等等，总结 Set 接口实现类，图如下：
由图中的继承关系，可以知道，Set 接口主要实现类有 AbstractSet、HashSet、LinkedHashSet 、TreeSet 、EnumSet（ RegularEnumSet、JumboEnumSet ），其中 AbstractSet、EnumSet 属于抽象类，EnumSet 是在 jdk1.5 中新增的，不同的是 EnumSet 集合元素必须是枚举类型。
HashSet 是一个输入输出无序的集合，集合中的元素基于 HashMap 的 key 实现，元素不可重复；
LinkedHashSet 是一个输入输出有序的集合，集合中的元素基于 LinkedHashMap 的 key 实现，元素也不可重复；
TreeSet 是一个排序的集合，集合中的元素基于 TreeMap 的 key 实现，同样元素不可重复；
EnumSet 是一个与枚举类型一起使用的专用 Set 集合，其中 RegularEnumSet 和 JumboEnumSet 不能单独实例化，只能由 EnumSet 来生成，同样元素不可重复；
下面咱们来对各个主要实现类进行一一分析！
HashSet 是一个输入输出无序的集合，底层基于 HashMap 来实现，HashSet 利用 HashMap 中的key元素来存放元素，这一点我们可以从源码上看出来，阅读源码如下：
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable{
}
打开HashSet的add()方法，源码如下：
public boolean add(E e) {
//向 HashMap 中添加元素
return map.put(e, PRESENT)==null;
}
其中变量PRESENT，是一个非空对象，源码部分如下：
private static final Object PRESENT = new Object();
可以分析出，当进行add()的时候，等价于
HashMap map = new HashMap<>();
map.put(e, new Object());//e 表示要添加的元素
在之前的集合文章中，咱们了解到 HashMap 在添加元素的时候 ，通过equals()和hashCode()方法来判断传入的key是否相同，如果相同，那么 HashMap 认为添加的是同一个元素，反之，则不是。
从源码分析上可以看出，HashSet 正是使用了 HashMap 的这一特性，实现存储元素下标无序、元素不会重复的特点。
HashSet 的删除方法，同样如此，也是基于 HashMap 的底层实现，源码如下：
public boolean remove(Object o) {
//调用HashMap 的remove方法，移除元素
return map.remove(o)==PRESENT;
}
HashSet 没有像 List、Map 那样提供 get 方法，而是使用迭代器或者 for 循环来遍历元素，方法如下：
public static void main(String[] args) {
Set<String> hashSet = new HashSet<String>();
System.out.println("HashSet初始容量大小："+hashSet.size());
hashSet.add("1");
hashSet.add("2");
hashSet.add("3");
hashSet.add("3");
hashSet.add("2");
hashSet.add(null);
}
输出结果：
HashSet初始容量大小：0
HashSet容量大小：4
null,1,2,3,
===========
null,1,2,3,
需要注意的是，HashSet 允许添加为null的元素。
LinkedHashSet 是一个输入输出有序的集合，继承自 HashSet，但是底层基于 LinkedHashMap 来实现。
如果你之前了解过 LinkedHashMap，那么你一定知道，它也继承自 HashMap，唯一有区别的是，LinkedHashMap 底层数据结构基于循环链表实现，并且数组指定了头部和尾部，虽然数组的下标存储无序，但是却可以通过数组的头部和尾部，加上循环链表，依次可以查询到元素存储的过程，从而做到输入输出有序的特点。
如果还不了解 LinkedHashMap 的实现过程，可以参阅集合系列中关于 LinkedHashMap 的实现过程文章。
阅读 LinkedHashSet 的源码，类定义如下：
public class LinkedHashSet<E>
extends HashSet<E>
implements Set<E>, Cloneable, java.io.Serializable {
}
查询源码，super调用的方法，源码如下：
HashSet(int initialCapacity, float loadFactor, boolean mmy) {
//初始化一个 LinkedHashMap
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
LinkedHshSet没有重写add方法，而是直接调用HashSet的add()方法，因为map的实现类是LinkedHashMap，所以此处是向LinkedHashMap中添加元素，当进行add()的时候，等价于
HashMap map = new LinkedHashMap<>();
map.put(e, new Object());//e 表示要添加的元素
LinkedHashSet也没有重写remove方法，而是直接调用HashSet的删除方法，因为LinkedHashMap没有重写remove方法，所以调用的也是HashMap的remove方法，源码如下：
public boolean remove(Object o) {
//调用HashMap 的remove方法，移除元素
return map.remove(o)==PRESENT;
}
同样的，LinkedHashSet 没有提供 get 方法，使用迭代器或者 for 循环来遍历元素，方法如下：
public static void main(String[] args) {
Set<String> linkedHashSet = new LinkedHashSet<String>();
System.out.println("linkedHashSet初始容量大小："+linkedHashSet.size());
linkedHashSet.add("1");
linkedHashSet.add("2");
linkedHashSet.add("3");
linkedHashSet.add("3");
linkedHashSet.add("2");
linkedHashSet.add(null);
linkedHashSet.add(null);
}
输出结果：
linkedHashSet初始容量大小：0
linkedHashSet容量大小：4
1,2,3,null,
===========
1,2,3,null,
可见，LinkedHashSet 与 HashSet 相比，LinkedHashSet 输入输出有序。
TreeSet 是一个排序的集合，实现了NavigableSet、SortedSet、Set接口，底层基于 TreeMap 来实现。TreeSet 利用 TreeMap 中的key元素来存放元素，这一点我们也可以从源码上看出来，阅读源码，类定义如下：
public class TreeSet<E> extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable {
}
new TreeSet<>()对象实例化的时候，表达的意思，可以简化为如下：
NavigableMap<E,Object> m = new TreeMap<E,Object>();
因为TreeMap实现了NavigableMap接口，所以没啥问题。
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable{
......
}
打开TreeSet的add()方法，源码如下：
public boolean add(E e) {
//向 TreeMap 中添加元素
return m.put(e, PRESENT)==null;
}
其中变量PRESENT，也是是一个非空对象，源码部分如下：
private static final Object PRESENT = new Object();
可以分析出，当进行add()的时候，等价于
TreeMap map = new TreeMap<>();
map.put(e, new Object());//e 表示要添加的元素
TreeMap 类主要功能在于，给添加的集合元素，按照一个的规则进行了排序，默认以自然顺序进行排序，当然也可以自定义排序，比如测试方法如下：
public static void main(String[] args) {
Map initMap = new TreeMap();
initMap.put("4", "d");
initMap.put("3", "c");
initMap.put("1", "a");
initMap.put("2", "b");
//默认自然排序，key为升序
System.out.println("默认 排序结果:" + initMap.toString());
//自定义排序，在TreeMap初始化阶段传入Comparator 内部对象
Map comparatorMap = new TreeMap<String, String>(new Comparator<String>() {
@Override
public int compare(String o1, String o2){
//根据key比较大小，采用倒叙，以大到小排序
return o2.compareTo(o1);
}
});
comparatorMap.put("4", "d");
comparatorMap.put("3", "c");
comparatorMap.put("1", "a");
comparatorMap.put("2", "b");
System.out.println("自定义 排序结果:" + comparatorMap.toString());
}
输出结果：
默认 排序结果:{1=a, 2=b, 3=c, 4=d}
自定义 排序结果:{4=d, 3=c, 2=b, 1=a}
相信使用过TreeMap的朋友，一定知道TreeMap会自动将key按照一定规则进行排序，TreeSet正是使用了TreeMap这种特性，来实现添加的元素集合，在输出的时候，其结果是已经排序好的。
如果您没看过源码TreeMap的实现过程，可以参阅集合系列文章中TreeMap的实现过程介绍，或者阅读 jdk 源码。
TreeSet 的删除方法，同样如此，也是基于 TreeMap 的底层实现，源码如下：
public boolean remove(Object o) {
//调用TreeMap 的remove方法，移除元素
return m.remove(o)==PRESENT;
}
TreeSet 没有重写 get 方法，而是使用迭代器或者 for 循环来遍历元素，方法如下：
public static void main(String[] args) {
Set<String> treeSet = new TreeSet<>();
System.out.println("treeSet初始容量大小："+treeSet.size());
treeSet.add("1");
treeSet.add("4");
treeSet.add("3");
treeSet.add("8");
treeSet.add("5");
}
输出结果：
treeSet初始容量大小：0
treeSet容量大小：5
1,3,4,5,8,
===========
1,3,4,5,8,
使用自定义排序，有 2 种方法，第一种在需要添加的元素类，实现Comparable接口，重写compareTo方法来实现对元素进行比较，实现自定义排序。
/**
创建一个Person实体类，实现Comparable接口，重写compareTo方法，通过变量age实现自定义排序 测试方法如下：
public static void main(String[] args) {
Set<Person> treeSet = new TreeSet<>();
System.out.println("treeSet初始容量大小："+treeSet.size());
treeSet.add(new Person("李一",18));
treeSet.add(new Person("李二",17));
treeSet.add(new Person("李三",19));
treeSet.add(new Person("李四",21));
treeSet.add(new Person("李五",20));
}
输出结果：
treeSet初始容量大小：0
treeSet容量大小：5
按照年龄从小到大，自定义排序结果：
李二:17,李一:18,李三:19,李五:20,李四:21,
第二种方法是在TreeSet初始化阶段，Person不用实现Comparable接口，将Comparator接口以内部类的形式作为参数，初始化进去，方法如下：
public static void main(String[] args) {
//自定义排序
Set<Person> treeSet = new TreeSet<>(new Comparator<Person>(){
@Override
public int compare(Person o1, Person o2) {
if(o1 == null || o2 == null){
//不用比较
return 0;
}
//从小到大进行排序
return o1.getAge() - o2.getAge();
}
});
System.out.println("treeSet初始容量大小："+treeSet.size());
treeSet.add(new Person("李一",18));
treeSet.add(new Person("李二",17));
treeSet.add(new Person("李三",19));
treeSet.add(new Person("李四",21));
treeSet.add(new Person("李五",20));
}
输出结果：
treeSet初始容量大小：0
treeSet容量大小：5
按照年龄从小到大，自定义排序结果：
李二:17,李一:18,李三:19,李五:20,李四:21,
需要注意的是，TreeSet不能添加为空的元素，否则会报空指针错误！
EnumSet 是一个与枚举类型一起使用的专用 Set 集合，继承自AbstractSet抽象类。与 HashSet、LinkedHashSet 、TreeSet 不同的是，EnumSet 元素必须是Enum的类型，并且所有元素都必须来自同一个枚举类型，EnumSet 定义源码如下：
public abstract class EnumSet<E extends Enum<E>> extends AbstractSet<E>
implements Cloneable, java.io.Serializable {
......
}
EnumSet是一个虚类，不能直接通过实例化来获取对象，只能通过它提供的静态方法来返回EnumSet实现类的实例。
EnumSet的实现类有两个，分别是RegularEnumSet、JumboEnumSet两个类，两个实现类都继承自EnumSet。
EnumSet会根据枚举类型中元素的个数，来决定是返回哪一个实现类，当 EnumSet元素中的元素个数小于或者等于64，就会返回RegularEnumSet实例；当EnumSet元素个数大于64，就会返回JumboEnumSet实例。
这一点，我们可以从源码中看出，源码如下：
public static <E extends Enum<E>> EnumSet<E> noneOf(Class<E> elementType) {
Enum<?>[] universe = getUniverse(elementType);
if (universe == null)
throw new ClassCastException(elementType + " not an enum");
//当元素个数小于或者等于 64 的时候，返回 RegularEnumSet
if (universe.length <= 64)
return new RegularEnumSet<>(elementType, universe);
else
//大于64，返回 JumboEnumSet
return new JumboEnumSet<>(elementType, universe);
}
noneOf是EnumSet中一个静态方法，用于判断是返回哪一个实现类。
我们来看看当元素个数小于等于64的时候，使用RegularEnumSet的类，源码如下：
class RegularEnumSet<E extends Enum<E>> extends EnumSet<E> {
}
RegularEnumSet 通过二进制运算得到结果，直接使用long来存放元素。
我们再来看看当元素个数大于64的时候，使用JumboEnumSet的类，源码如下：
class JumboEnumSet<E extends Enum<E>> extends EnumSet<E> {
}
JumboEnumSet 也是通过二进制运算得到结果，使用long来存放元素，但是它是使用数组来存放元素。
二者相比，RegularEnumSet 效率比 JumboEnumSet 高些，因为操作步骤少，大多数情况下返回的是 RegularEnumSet，只有当枚举元素个数超过 64 的时候，会使用 JumboEnumSet。
添加元素：
//新建一个EnumEntity的枚举类型，定义2个参数
public enum EnumEntity {
WOMAN,MAN;
}
创建一个空的 EnumSet：
//创建一个 EnumSet，内容为空
EnumSet<EnumEntity> noneSet = EnumSet.noneOf(EnumEntity.class);
System.out.println(noneSet);
输出结果：
[]
创建一个 EnumSet，并将枚举类型的元素全部添加进去：
//创建一个 EnumSet，将EnumEntity 元素内容添加到EnumSet中
EnumSet<EnumEntity> allSet = EnumSet.allOf(EnumEntity.class);
System.out.println(allSet);
输出结果：
[WOMAN, MAN]
创建一个 EnumSet，添加指定的枚举元素：
//创建一个 EnumSet，添加 WOMAN 到 EnumSet 中
EnumSet<EnumEntity> customSet = EnumSet.of(EnumEntity.WOMAN);
System.out.println(customSet);
查询元素
EnumSet与HashSet、LinkedHashSet、TreeSet一样，通过迭代器或者 for 循环来遍历元素，方法如下：
EnumSet<EnumEntity> allSet = EnumSet.allOf(EnumEntity.class);
for (EnumEntity enumEntity : allSet) {
System.out.print(enumEntity + ",");
}
输出结果：
WOMAN,MAN,
HashSet 是一个输入输出无序的 Set 集合，元素不重复，底层基于 HashMap 的 key 来实现，元素可以为空，如果添加的元素为对象，对象需要重写 equals() 和 hashCode() 方法来约束是否为相同的元素。
LinkedHashSet 是一个输入输出有序的 Set 集合，继承自 HashSet，元素不重复，底层基于 LinkedHashMap 的 key来实现，元素也可以为空，LinkedHashMap 使用循环链表结构来保证输入输出有序。
TreeSet 是一个排序的 Set 集合，元素不可重复，底层基于 TreeMap 的 key来实现，元素不可以为空，默认按照自然排序来存放元素，也可以使用 Comparable 和 Comparator 接口来比较大小，实现自定义排序。
EnumSet 是一个与枚举类型搭配使用的专用 Set 集合，在 jdk1.5 中加入。EnumSet 是一个虚类，有2个实现类 RegularEnumSet、JumboEnumSet，不能显式的实例化改类，EnumSet 会动态决定使用哪一个实现类，当元素个数小于等于64的时候，使用 RegularEnumSet；大于 64的时候，使用JumboEnumSet类，EnumSet 其内部使用位向量实现，拥有极高的时间和空间性能，如果元素是枚举类型，推荐使用 EnumSet。
1、JDK1.7&JDK1.8 源码
2、程序园 - java集合－EnumMap与EnumSet
3、 Java极客技术 - https://blog.csdn.net/javageektech/article/details/103077788
Ⅲ 求java里面的Hash<Map>的用法和基本解释，谢谢
HashMap 和 HashSet 是 Java Collection Framework 的两个重要成员，其中 HashMap 是 Map 接口的常用实现类，HashSet 是 Set 接口的常用实现类。虽然 HashMap 和 HashSet 实现的接口规范不同，但它们底层的 Hash 存储机制完全一样，甚至 HashSet 本身就采用 HashMap 来实现的。
通过 HashMap、HashSet 的源代码分析其 Hash 存储机制
实际上，HashSet 和 HashMap 之间有很多相似之处，对于 HashSet 而言，系统采用 Hash 算法决定集合元素的存储位置，这样可以保证能快速存、取集合元素；对于 HashMap 而言，系统 key-value 当成一个整体进行处理，系统总是根据 Hash 算法来计算 key-value 的存储位置，这样可以保证能快速存、取 Map 的 key-value 对。
在介绍集合存储之前需要指出一点：虽然集合号称存储的是 Java 对象，但实际上并不会真正将 Java 对象放入 Set 集合中，只是在 Set 集合中保留这些对象的引用而言。也就是说：Java 集合实际上是多个引用变量所组成的集合，这些引用变量指向实际的 Java 对象。
集合和引用
就像引用类型的数组一样，当我们把 Java 对象放入数组之时，并不是真正的把 Java 对象放入数组中，只是把对象的引用放入数组中，每个数组元素都是一个引用变量。
HashMap 的存储实现
当程序试图将多个 key-value 放入 HashMap 中时，以如下代码片段为例：
Java代码
HashMap<String , Double> map = new HashMap<String , Double>();
map.put("语文" , 80.0);
map.put("数学" , 89.0);
map.put("英语" , 78.2);
HashMap 采用一种所谓的“Hash 算法”来决定每个元素的存储位置。
当程序执行 map.put("语文" , 80.0); 时，系统将调用"语文"的 hashCode() 方法得到其 hashCode 值——每个 Java 对象都有 hashCode() 方法，都可通过该方法获得它的 hashCode 值。得到这个对象的 hashCode 值之后，系统会根据该 hashCode 值来决定该元素的存储位置。
我们可以看 HashMap 类的 put(K key , V value) 方法的源代码：
Java代码
public V put(K key, V value)
{
// 如果 key 为 null，调用 putForNullKey 方法进行处理
if (key == null)
return putForNullKey(value);
// 根据 key 的 keyCode 计算 Hash 值
int hash = hash(key.hashCode());
// 搜索指定 hash 值在对应 table 中的索引
int i = indexFor(hash, table.length);
// 如果 i 索引处的 Entry 不为 null，通过循环不断遍历 e 元素的下一个元素
for (Entry<K,V> e = table[i]; e != null; e = e.next)
{
Object k;
// 找到指定 key 与需要放入的 key 相等（hash 值相同
// 通过 equals 比较放回 true）
if (e.hash == hash && ((k = e.key) == key
|| key.equals(k)))
{
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
// 如果 i 索引处的 Entry 为 null，表明此处还没有 Entry
modCount++;
// 将 key、value 添加到 i 索引处
addEntry(hash, key, value, i);
return null;
}
上面程序中用到了一个重要的内部接口：Map.Entry，每个 Map.Entry 其实就是一个 key-value 对。从上面程序中可以看出：当系统决定存储 HashMap 中的 key-value 对时，完全没有考虑 Entry 中的 value，仅仅只是根据 key 来计算并决定每个 Entry 的存储位置。这也说明了前面的结论：我们完全可以把 Map 集合中的 value 当成 key 的附属，当系统决定了 key 的存储位置之后，value 随之保存在那里即可。
上面方法提供了一个根据 hashCode() 返回值来计算 Hash 码的方法：hash()，这个方法是一个纯粹的数学计算，其方法如下：
Java代码
static int hash(int h)
{
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
对于任意给定的对象，只要它的 hashCode() 返回值相同，那么程序调用 hash(int h) 方法所计算得到的 Hash 码值总是相同的。接下来程序会调用 indexFor(int h, int length) 方法来计算该对象应该保存在 table 数组的哪个索引处。indexFor(int h, int length) 方法的代码如下：
Java代码
static int indexFor(int h, int length)
{
return h & (length-1);
}
这个方法非常巧妙，它总是通过 h &(table.length -1) 来得到该对象的保存位置——而 HashMap 底层数组的长度总是 2 的 n 次方，这一点可参看后面关于 HashMap 构造器的介绍。
当 length 总是 2 的倍数时，h & (length-1) 将是一个非常巧妙的设计：假设 h=5,length=16, 那么 h & length - 1 将得到 5；如果 h=6,length=16, 那么 h & length - 1 将得到 6 ……如果 h=15,length=16, 那么 h & length - 1 将得到 15；但是当 h=16 时 , length=16 时，那么 h & length - 1 将得到 0 了；当 h=17 时 , length=16 时，那么 h & length - 1 将得到 1 了……这样保证计算得到的索引值总是位于 table 数组的索引之内。
根据上面 put 方法的源代码可以看出，当程序试图将一个 key-value 对放入 HashMap 中时，程序首先根据该 key 的 hashCode() 返回值决定该 Entry 的存储位置：如果两个 Entry 的 key 的 hashCode() 返回值相同，那它们的存储位置相同。如果这两个 Entry 的 key 通过 equals 比较返回 true，新添加 Entry 的 value 将覆盖集合中原有 Entry 的 value，但 key 不会覆盖。如果这两个 Entry 的 key 通过 equals 比较返回 false，新添加的 Entry 将与集合中原有 Entry 形成 Entry 链，而且新添加的 Entry 位于 Entry 链的头部——具体说明继续看 addEntry() 方法的说明。
当向 HashMap 中添加 key-value 对，由其 key 的 hashCode() 返回值决定该 key-value 对（就是 Entry 对象）的存储位置。当两个 Entry 对象的 key 的 hashCode() 返回值相同时，将由 key 通过 eqauls() 比较值决定是采用覆盖行为（返回 true），还是产生 Entry 链（返回 false）。
上面程序中还调用了 addEntry(hash, key, value, i); 代码，其中 addEntry 是 HashMap 提供的一个包访问权限的方法，该方法仅用于添加一个 key-value 对。下面是该方法的代码：
Java代码
void addEntry(int hash, K key, V value, int bucketIndex)
{
// 获取指定 bucketIndex 索引处的 Entry
Entry<K,V> e = table[bucketIndex]; // ①
// 将新创建的 Entry 放入 bucketIndex 索引处，并让新的 Entry 指向原来的 Entry
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
// 如果 Map 中的 key-value 对的数量超过了极限
if (size++ >= threshold)
// 把 table 对象的长度扩充到 2 倍。
resize(2 * table.length); // ②
}
上面方法的代码很简单，但其中包含了一个非常优雅的设计：系统总是将新添加的 Entry 对象放入 table 数组的 bucketIndex 索引处——如果 bucketIndex 索引处已经有了一个 Entry 对象，那新添加的 Entry 对象指向原有的 Entry 对象（产生一个 Entry 链），如果 bucketIndex 索引处没有 Entry 对象，也就是上面程序①号代码的 e 变量是 null，也就是新放入的 Entry 对象指向 null，也就是没有产生 Entry 链。
JDK 源码
在 JDK 安装目录下可以找到一个 src.zip 压缩文件，该文件里包含了 Java 基础类库的所有源文件。只要读者有学习兴趣，随时可以打开这份压缩文件来阅读 Java 类库的源代码，这对提高读者的编程能力是非常有帮助的。需要指出的是：src.zip 中包含的源代码并没有包含像上文中的中文注释，这些注释是笔者自己添加进去的。
Hash 算法的性能选项
根据上面代码可以看出，在同一个 bucket 存储 Entry 链的情况下，新放入的 Entry 总是位于 bucket 中，而最早放入该 bucket 中的 Entry 则位于这个 Entry 链的最末端。
上面程序中还有这样两个变量：
* size：该变量保存了该 HashMap 中所包含的 key-value 对的数量。
* threshold：该变量包含了 HashMap 能容纳的 key-value 对的极限，它的值等于 HashMap 的容量乘以负载因子（load factor）。
从上面程序中②号代码可以看出，当 size++ >= threshold 时，HashMap 会自动调用 resize 方法扩充 HashMap 的容量。每扩充一次，HashMap 的容量就增大一倍。
上面程序中使用的 table 其实就是一个普通数组，每个数组都有一个固定的长度，这个数组的长度就是 HashMap 的容量。HashMap 包含如下几个构造器：
* HashMap()：构建一个初始容量为 16，负载因子为 0.75 的 HashMap。
* HashMap(int initialCapacity)：构建一个初始容量为 initialCapacity，负载因子为 0.75 的 HashMap。
* HashMap(int initialCapacity, float loadFactor)：以指定初始容量、指定的负载因子创建一个 HashMap。
当创建一个 HashMap 时，系统会自动创建一个 table 数组来保存 HashMap 中的 Entry，下面是 HashMap 中一个构造器的代码：
Java代码
// 以指定初始化容量、负载因子创建 HashMap
public HashMap(int initialCapacity, float loadFactor)
{
// 初始容量不能为负数
if (initialCapacity < 0)
throw new IllegalArgumentException(
"Illegal initial capacity: " +
initialCapacity);
// 如果初始容量大于最大容量，让出示容量
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
// 负载因子必须大于 0 的数值
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException(
loadFactor);
// 计算出大于 initialCapacity 的最小的 2 的 n 次方值。
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
this.loadFactor = loadFactor;
// 设置容量极限等于容量 * 负载因子
threshold = (int)(capacity * loadFactor);
// 初始化 table 数组
table = new Entry[capacity]; // ①
init();
}
上面代码中粗体字代码包含了一个简洁的代码实现：找出大于 initialCapacity 的、最小的 2 的 n 次方值，并将其作为 HashMap 的实际容量（由 capacity 变量保存）。例如给定 initialCapacity 为 10，那么该 HashMap 的实际容量就是 16。
程序①号代码处可以看到：table 的实质就是一个数组，一个长度为 capacity 的数组。
对于 HashMap 及其子类而言，它们采用 Hash 算法来决定集合中元素的存储位置。当系统开始初始化 HashMap 时，系统会创建一个长度为 capacity 的 Entry 数组，这个数组里可以存储元素的位置被称为“桶（bucket）”，每个 bucket 都有其指定索引，系统可以根据其索引快速访问该 bucket 里存储的元素。
无论何时，HashMap 的每个“桶”只存储一个元素（也就是一个 Entry），由于 Entry 对象可以包含一个引用变量（就是 Entry 构造器的的最后一个参数）用于指向下一个 Entry，因此可能出现的情况是：HashMap 的 bucket 中只有一个 Entry，但这个 Entry 指向另一个 Entry ——这就形成了一个 Entry 链。如图 1 所示：
图 1. HashMap 的存储示意
HashMap 的读取实现
当 HashMap 的每个 bucket 里存储的 Entry 只是单个 Entry ——也就是没有通过指针产生 Entry 链时，此时的 HashMap 具有最好的性能：当程序通过 key 取出对应 value 时，系统只要先计算出该 key 的 hashCode() 返回值，在根据该 hashCode 返回值找出该 key 在 table 数组中的索引，然后取出该索引处的 Entry，最后返回该 key 对应的 value 即可。看 HashMap 类的 get(K key) 方法代码：
Java代码
public V get(Object key)
{
// 如果 key 是 null，调用 getForNullKey 取出对应的 value
if (key == null)
return getForNullKey();
// 根据该 key 的 hashCode 值计算它的 hash 码
int hash = hash(key.hashCode());
// 直接取出 table 数组中指定索引处的值，
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
// 搜索该 Entry 链的下一个 Entr
e = e.next) // ①
{
Object k;
// 如果该 Entry 的 key 与被搜索 key 相同
if (e.hash == hash && ((k = e.key) == key
|| key.equals(k)))
return e.value;
}
return null;
}
从上面代码中可以看出，如果 HashMap 的每个 bucket 里只有一个 Entry 时，HashMap 可以根据索引、快速地取出该 bucket 里的 Entry；在发生“Hash 冲突”的情况下，单个 bucket 里存储的不是一个 Entry，而是一个 Entry 链，系统只能必须按顺序遍历每个 Entry，直到找到想搜索的 Entry 为止——如果恰好要搜索的 Entry 位于该 Entry 链的最末端（该 Entry 是最早放入该 bucket 中），那系统必须循环到最后才能找到该元素。
归纳起来简单地说，HashMap 在底层将 key-value 当成一个整体进行处理，这个整体就是一个 Entry 对象。HashMap 底层采用一个 Entry[] 数组来保存所有的 key-value 对，当需要存储一个 Entry 对象时，会根据 Hash 算法来决定其存储位置；当需要取出一个 Entry 时，也会根据 Hash 算法找到其存储位置，直接取出该 Entry。由此可见：HashMap 之所以能快速存、取它所包含的 Entry，完全类似于现实生活中母亲从小教我们的：不同的东西要放在不同的位置，需要时才能快速找到它。
当创建 HashMap 时，有一个默认的负载因子（load factor），其默认值为 0.75，这是时间和空间成本上一种折衷：增大负载因子可以减少 Hash 表（就是那个 Entry 数组）所占用的内存空间，但会增加查询数据的时间开销，而查询是最频繁的的操作（HashMap 的 get() 与 put() 方法都要用到查询）；减小负载因子会提高数据查询的性能，但会增加 Hash 表所占用的内存空间。
掌握了上面知识之后，我们可以在创建 HashMap 时根据实际需要适当地调整 load factor 的值；如果程序比较关心空间开销、内存比较紧张，可以适当地增加负载因子；如果程序比较关心时间开销，内存比较宽裕则可以适当的减少负载因子。通常情况下，程序员无需改变负载因子的值。
如果开始就知道 HashMap 会保存多个 key-value 对，可以在创建时就使用较大的初始化容量，如果 HashMap 中 Entry 的数量一直不会超过极限容量（capacity * load factor），HashMap 就无需调用 resize() 方法重新分配 table 数组，从而保证较好的性能。当然，开始就将初始容量设置太高可能会浪费空间（系统需要创建一个长度为 capacity 的 Entry 数组），因此创建 HashMap 时初始化容量设置也需要小心对待。
Ⅳ 面试官：HashSet如何保证元素不重复
HashSet 实现了 Set 接口，由哈希表（实际是 HashMap）提供支持。HashSet 不保证集合的迭代顺序，但允许插入 null 值。这意味着它可以将集合中的重复元素自动过滤掉，保证存储在 HashSet 中的元素都是唯一的。
HashSet 基本操作方法有：add（添加）、remove（删除）、contains（判断某个元素是否存在）和 size（集合数量）。这些方法的性能都是固定操作时间，如果哈希函数是将元素分散在桶中的正确位置。HashSet 的基本使用方式如下：
HashSet 不能保证插入元素的顺序和循环输出元素的顺序一致，实际上，HashSet 是无序的集合。具体代码示例如下：
这表明，HashSet 的插入顺序为：深圳 -> 北京 -> 西安，而循环打印的顺序是：西安 -> 深圳 -> 北京。因此，HashSet 是无序的，不能保证插入和迭代的顺序一致。
如果要保证插入顺序和迭代顺序一致，可以使用 LinkedHashSet 替换 HashSet。
有人说 HashSet 只能保证基础数据类型不重复，却不能保证自定义对象不重复？其实不是这样的。使用 HashSet 存储基本数据类型，可以实现去重。将自定义对象存储到 HashSet 中时，HashSet 会依赖元素的 hashCode 和 equals 方法判断元素是否重复。如果两个对象的 hashCode 和 equals 返回 true，说明它们是相同的对象。例如，Long 类型元素之所以能实现去重，是因为 Long 类型中已经重写了 hashCode 和 equals 方法。
为了使 HashSet 支持自定义对象去重，只需在自定义对象中重写 hashCode 和 equals 方法即可。这样，HashSet 就可以根据对象的 hashCode 和 equals 判断是否重复，从而实现自定义对象的去重。
HashSet 保证元素不重复是通过计算对象的 hashcode 值来判断对象的存储位置。当添加对象时，HashSet 首先计算对象的 hashcode 值，然后与其他对象的 hashcode 值进行比较。如果发现相同 hashcode 值的对象，HashSet 会调用对象的 equals() 方法来检查对象是否相同。如果相同，则不会让重复的对象加入到 HashSet 中，这样就保证了元素的不重复。具体实现源码基于 JDK 8，HashSet 的 add 方法实际调用了 HashMap 的 put 方法，而 put 方法又调用了 putVal 方法。在 putVal 方法中，首先根据 key 的 hashCode 返回值决定 Entry 的存储位置。如果有两个 key 的 hash 值相同，则会判断这两个元素 key 的 equals() 是否相同。如果相同，说明是重复键值对，HashSet 的 add 方法会返回 false，表示添加元素失败。如果 key 不重复，put 方法最终会返回 null，表示添加成功。
总结而言，HashSet 底层是由 HashMap 实现的，它可以实现重复元素的去重功能。如果存储的是自定义对象，必须重写 hashCode 和 equals 方法。HashSet 通过在存储之前判断 key 的 hashCode 和 equals 来保证元素的不重复。