Thinking in java：17 容器深入研究
1. Set和存储顺序
2. 理解Map
再次强调默认的Object.equal()只是比较对象的地址，所以如果要用自己的类作为HashMap的键，必须同时重载hashCode（）和equal（）方法。
3. 理解hashCode（）
使用散列的目的在于：想要使用一个对象来查找另一个对象。散列的价值在于速度（为什么使用散列）：散列使得查询得以快速进行。
我们知道存储一组元素最快的数据结构是数组，所以使用数组来表示键的信息（并非键本身）。通过键对象生成一个数字（称为散列码，即hashCode（）方法生成的数字），将其作为数组的下标。而这个数组中存放的是值的List，因为相同散列码的键所对应的值都存放在数组的这个下标中。不同的键可以产生相同的下标（散列码）。于是查询一个值的过程就是，使用hashCode方法计算出此键的散列码，那么就知道值所在的数组下标，然后到此下标中的List中使用equals（）方法进行线性查询。
HashMap其实就是数组+List实现的。
那么设计hashCode（）时最重要的元素是：无论何时，对同一个对象调用hashCode（）方法都应生成同样的值。另外一个，好的hashCode（）应该产生均匀分布的散列码。
4. 为什么HashMap是线程不安全的？
因为HashMap底层维护了一个数组，当多线程时对这个数组的操作是不安全的。
5. 不同接口的选择
5.1 对List的选择
将ArrayList作为默认首选，当程序需要经常从表中间进行插入和删除时才选用LinkedList。
需要进行随机访问是，例如put（）和set（）操作时，和查询时，一般ArrayList的速度快，需要频繁插入和删除时，LinkedList的速度快。原因：ArrayList底层是数组支持，LinkedList是由双向链表实现的。ArrayList在插入时，必须创建空间并将移动它的引用，所以代价高。而LinkedList只需链接新的元素，而不必修改列表中的剩余元素，所以无论尺寸如何变化，其代价大致相同。
5.2 对Set的选择
HashSet的性能基本上总是比TreeSet好，特别是在添加和查询元素时，而这两个操作也是最重要的操作。TreeSet存在的唯一原因是它可以维持元素的排序状态。
HashSet的实现原理总结如下：
①是基于HashMap实现的，默认构造函数是构建一个初始容量为16，负载因子为0.75 的HashMap。封装了一个 HashMap 对象来存储所有的集合元素，所有放入 HashSet 中的集合元素实际上由 HashMap 的 key 来保存，而 HashMap 的 value 则存储了一个 PRESENT，它是一个静态的 Object 对象。
②当我们试图把某个类的对象当成 HashMap的 key，或试图将这个类的对象放入 HashSet 中保存时，重写该类的equals(Object obj)方法和 hashCode() 方法很重要，而且这两个方法的返回值必须保持一致：当该类的两个的 hashCode() 返回值相同时，它们通过 equals() 方法比较也应该返回 true。通常来说，所有参与计算 hashCode() 返回值的关键属性，都应该用于作为 equals() 比较的标准。
③HashSet的其他操作都是基于HashMap的。
LinkedHashSet
是基于链表实现的。对于插入操作，LinkedHashSet比HashSet的代价更高，这是由于维护链表所带来的额外开销造成的。
HashSet导致的内存泄漏
把一个对象存储进hashSet集合后，修改这个对象中参与计算hash的变量的值，这时这个对象的hash值也会随之改变，那么这么对象可以正常地被删除吗？下面用代码试一下：
public class MPoint {
private int x;
private int y;
public MPoint() {
}
public MPoint( int x, int y) {
this. x = x;
this. y = y;
}
public int getX() {
return x;
}
public void setX(int x) {
this. x = x;
}
public int getY() {
return y;
}
public void setY(int y) {
this. y = y;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + x; //x参与计算hash值
return result;
}
@Override
public boolean equals(Object obj) {
if ( this == obj)
return true;
if ( obj == null)
return false;
if (getClass() != obj.getClass())
return false;
MPoint other = (MPoint) obj;
if ( x != other. x)
return false;
if ( y != other. y)
return false;
return true;
}
} 主函数类测试，在一个HashSet集合中添加三个元素，mp1、mp2、mp3，并进行其中属性的修改和输出测试
public class HashSetTest {
public static void main(String[] args) {
HashSet<MPoint> set = new HashSet<MPoint>();
MPoint mp1 = new MPoint(1, 6);
MPoint mp2 = new MPoint(2, 7);
MPoint mp3 = new MPoint(1, 6);
set.add( mp1);
set.add( mp2);
set.add( mp3);
set.add( mp1);
System. out.println( set.size()); // 结果为2
mp1.setX(3);
set.remove( mp1);
System. out.println( set.size()); // 结果还是为2，说明没有删除成功
System. out.println( set.contains( mp1)); // 结果为false，修改了参与计算hash值的变量，其对象不能再被找到
System. out.println( set.remove( mp1)); // 结果为false，修改了参与计算hash值的变量，其对象不能被删除
mp2.setY(2);
System. out.println( set.contains( mp2)); // 结果为true，没有修改关键属性的对象可以被找到
System. out.println( set.remove( mp2)); // 结果为true，没有修改关键属性的对象可以被删除
System. out.println( set.size()); // 结果还是为1
}
} 输出：
2
2
false
false
true
true
1 可以看出已经发生了内存泄漏了，mp1对象不能被正常删除。
5.3 对Map的选择
除了IdentityHashMap，所有的Map实现的插入操作都会随着Map尺寸的变大而明显变慢。但是，查找的代价通常比插入要小得多，这是个好消息，因为我们执行查找元素的操作要比执行插入元素的操作多得多。
HashMap与Hashtable的性能大体相当。因为HashMap是用来替代Hashtable的，他们使用相同的底层存储和查找机制。
TreeMap通常比HashMap慢，但它能根据key来排序。
LinkedHashMap在插入时比HashMap慢一点，因为它维护散列数据结构的同时还要维护链表（以保证插入顺序）。正是由于这个列表，使得其迭代速度更快。LinkedHashMap是HashMap的一个子类，它保留插入的顺序。LinkedHashMap是Map接口的哈希表和链接列表实现，具有可预知的迭代顺序。 LinkedHashMap实现与HashMap的不同之处在于，后者维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序可以是插入顺序或者是访问顺序。
HashMap的性能因子：
负载因子：尺寸/容量。负载轻的表产生冲突的可能性小。当达到负载因子的水平时，容器自动增加其容量，并重新将现有对象分布到新的桶位集中，这被称为“再散列”。
桶：一个数组的某一项就是一个桶，如a[0]、a[1]都是桶
上一篇： 【Linux】gdb调试多进程多线程