public class HashSet
extends AbstractSet
implements Set, Cloneable, java.io.Serializable
{
private static final Object PRESENT = new Object();
public HashSet() {
map = new HashMap<>();
}
public HashSet(Collection<? extends E> c) {
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}
}
由上面源程序可以看出，HashSet 的实现其实非常简单，它只是封装了一个 HashMap 对象来存储所有的集合元素，所有放入 HashSet 中的集合元素实际上由 HashMap 的 key 来保存，而 HashMap 的 value 则存储了一个 PRESENT，它是一个静态的
Object 对象。
##5.HashMap与HashTable
public class Hashtable
1.HashTable是一个线程安全的API，它的方法通过synchronized关键字进行修饰。尽管并不推荐使用HashTable来开发一个高性能的应用，但是它确实能够保证你的应用线程安全。相反，HashMap并不保证线程安全。因此当你构建一个多线程应用时，请使用ConcurrentHashMap。
2.关联数组与数组最大的不同，就是对于每一个数据，关联数组会有一个key与之关联，当使用关联数组时，每个数据都可以通过对应的Key来获取。关联数组有许多别名，比如Map（映射）、Dictionary（字典）和Symbol-Table（符号表）。尽管名字不同，他们的含义都是相同的。
3.字典和符号表都是非常直观的术语，无须解释它们的行为。映射来自于数学领域。在函数中，一个域（集合）中的值被与另一个域（集合）中的值关联，这种关联关系叫做映射。
##6 HashMap与线程安全
HashMap底层的数据结构是一个Entry数组，通过对key值进行hash映射，确定key-value对的存放位置。当多个不同key映射到同一个hash值时，它们在Entry数组中以链表的形式存在，新加入的元素会放在链表的头部。
可见HashMap的线程不安全的主要原因是HashMap的结构发生了变化，而从上一篇文章中可以知道，HashMap的结构变化发生在数组容量变更时，即当数组元素个数超过了阈值threshold=capacity*loadFactor时，HashMap将resize()
#####2.2.3.1单线程下单扩容
#####2.2.3.2多线程下单扩容
#####2.2.3.3线程不安全的表现
1、多线程put操作后，
get操作导致死循环。
2、多线程put非NULL元素后，
get操作得到NULL值。
3、多线程put操作，导致元素丢失。
###如何安全的使用HashMap
1.Hashtable
2.ConcurrentHashMap
3.Synchronized Map
###Hashtable
HashMap是Java
1.2引进的Map接口的一个实现。HashMap是新框架中用来代替Hashtable的类，也就是说建议使用HashMap，不要使用Hashtable。
Hashtable的方法是同步的，HashMap未经同步，所以在多线程场合要手动同步HashMap这个区别就像Vector和ArrayList一样。查看Hashtable的源代码就可以发现，除构造函数外，Hashtable的所有
public 方法声明中都有 synchronized 关键字，而HashMap的源代码中则连 synchronized 的影子都没有，当然，注释除外。HashTable源码中是使用synchronized来保证线程安全的，
###ConcurrentHashMap
多线程操作要格外小心。知道JDK
1.5引入了ConcurrentHashMap才使得Map重新能够安全的在多线程下操作了。
ConcurrentHashMap具体是怎么实现线程安全的呢，肯定不可能是每个方法加synchronized，那样就变成了HashTable。
从ConcurrentHashMap代码中可以看出，它引入了一个“分段锁”的概念，具体可以理解为把一个大的Map拆分成N个小的HashTable，根据key.hashCode()来决定把key放到哪个HashTable中。
在ConcurrentHashMap中，就是把Map分成了N个Segment，put和
get的时候，都是现根据key.hashCode()算出放到哪个Segment中：
###SynchronizedMap
/**
*性能对比例程
*/
public class CrunchifyConcurrentHashMapVsSynchronizedMap {
public final static int THREAD_POOL_SIZE = 5;
public static Map<String, Integer> crunchifyHashTableObject = null;
public static Map<String, Integer> crunchifySynchronizedMapObject = null;
public static Map<String, Integer> crunchifyConcurrentHashMapObject = null;
public static void main(String[] args) throws InterruptedException {
// Test with Hashtable Object
crunchifyHashTableObject = new Hashtable<>();
crunchifyPerformTest(crunchifyHashTableObject);
// Test with synchronizedMap Object
crunchifySynchronizedMapObject = Collections.synchronizedMap(new HashMap<String, Integer>());
crunchifyPerformTest(crunchifySynchronizedMapObject);
// Test with ConcurrentHashMap Object
crunchifyConcurrentHashMapObject = new ConcurrentHashMap<>();
crunchifyPerformTest(crunchifyConcurrentHashMapObject);
}
public static void crunchifyPerformTest(final Map<String, Integer> crunchifyThreads) throws InterruptedException {
System.out.println("Test started for: " + crunchifyThreads.getClass());
long averageTime = 0;
for (int i = 0; i < 5; i++) {
long startTime = System.nanoTime();
ExecutorService crunchifyExServer = Executors.newFixedThreadPool(THREAD_POOL_SIZE);
for (int j = 0; j < THREAD_POOL_SIZE; j++) {
crunchifyExServer.execute(new Runnable() {
@SuppressWarnings("unused")
@Override
public void run() {
for (int i = 0; i < 500000; i++) {
Integer crunchifyRandomNumber = (int) Math.ceil(Math.random() * 550000);
// Retrieve value. We are not using it anywhere
Integer crunchifyValue = crunchifyThreads.get(String.valueOf(crunchifyRandomNumber));
// Put value
crunchifyThreads.put(String.valueOf(crunchifyRandomNumber), crunchifyRandomNumber);
}
}
});
}
// Make sure executor stops
crunchifyExServer.shutdown();
// Blocks until all tasks have completed execution after a shutdown request
crunchifyExServer.awaitTermination(Long.MAX_VALUE, TimeUnit.DAYS);
long entTime = System.nanoTime();
long totalTime = (entTime - startTime) / 1000000L;
averageTime += totalTime;
System.out.println("2500K entried added/retrieved in " + totalTime + " ms");
}
System.out.println("For " + crunchifyThreads.getClass() + " the average time is " + averageTime / 5 + " ms\n");
}
