ConcurrentHashMap, Hashtable and HashMap

1.
default initial capacity, HashMap is 16, Hashtable is 11(eleven).
而且HashMap的capacity应该是2的指数倍的，它还有MAXIMUM_CAPACITY。
HashMap的构造函数中还会调用一个init()方法，这个默认是空的，是留给子类来做个性化定义的。
DEFAULT_LOAD_FACTOR is 0.75f for these two.
ConcurrentHashMap的capacity方面设置和HashMap类似。
AbstractConcurrentReadCache也是map类的，默认capacity是16，最大值是1<<30, 默认factor 0.75。

2.
它们其实都是维护一个数组，数组中每个元素是一个单向链表。根据hashCode然后计算出数组中的index。
取index的算法不同：
HashMap，ConcurrentHashMap:
h & (length-1);  //这里h是改进后的hashCode,
// Entry 的hashCode：
return (key==NULL_KEY ? 0 : key.hashCode()) ^
       (value==null   ? 0 : value.hashCode());

static int hash(Object x) {
        int h = x.hashCode();

        h += ~(h << 9);
        h ^=  (h >>> 14);
        h +=  (h << 4);
        h ^=  (h >>> 10);
        return h;
    }//谁能告诉我这里怎么理解？这个算法？
                
Hashtable:
int index = (hash & 0x7FFFFFFF) % tab.length;    //length默认是11，是个质数，所以是有意义的

ConcurrentHashMap计算index的方法是和HashMap一样的


3.对于拷贝构造函数：
public HashMap(Map<? extends K, ? extends V> m) {
  this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
      DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
  putAllForCreate(m);
}
public Hashtable(Map<? extends K, ? extends V> t) {
  this(Math.max(2*t.size(), 11), 0.75f);  //为什么是2倍呢，不是t.size()/0.75?
  putAll(t);
}

public ConcurrentHashMap(Map<? extends K, ? extends V> t) {
  this(Math.max((int) (t.size() / DEFAULT_LOAD_FACTOR) + 1,11),
      DEFAULT_LOAD_FACTOR, DEFAULT_SEGMENTS);
  putAll(t);
}

4.最重要的是并发啊
HashMap没有做任何并发
Hashtable是在接口一级用synchronized实现互斥的，例如size(), isEmpty(),put,putAll(),get(key),containsKey,contains，toString，remove,clone()，writeObject 都有synchronized关键字修饰的。包括读，写操作，因为防止读不一致。
Hashtable中的每次put操作，还要检查是否容量超出范围，如果是，则要rehash

ConcurrentHashMap是引入了Segment，每个Segment有是一个hashtable，相当于是两级Hash表，然后锁是在Segment一级进行的，提高了并发性。
final Segment<K,V> segmentFor(int hash) {
  return (Segment<K,V>) segments[(hash >>> segmentShift) & segmentMask];
}
ConcurrentHashMap 中的Segment中：
read不加锁，只有在读到null的情况(一般不会有null的，只有在其他线程操作Map的时候，所以就用锁来等他操作完）下调用了readValueUnderLock，这里面用到了锁。
write(包括replace,put,remove) 操作加锁

但rehash()方法不加锁
??remove方法中不是用一般的链表的remove的方法，而是将要删除的节点（e）之前的node全部复制到e的后面

abcdefghi=> edcbafghi=>然后以d为头付给tab[index]
这个的目的就是，在操作过程中不去改next指针，所以都是从链表头来进行操作，包括put也是，只能put到链表的头。
为什么这样呢，再来看一下HashEntry的定义，其他都是final的，只有value不是，它是volatile的，所以next是不能改的。
   static final class HashEntry<K,V> {  
        final K key;  
        final int hash;  
        volatile V value;  
        final HashEntry<K,V> next;  
   } 
final定义使得在构造函数执行过程中，内存分配好后，一定要先赋值后才会把指针引用到，那么其他线程看到这个对象的时候，这个值一定会有的，而value就不一定了，所以才有用个readValueUnderLock方法做备份的做法。
另外volatile关键字还保证读线程一定会等写线程执行完了才会读到，这样一定是读到最新的数据的。这样实现了read操作不需要锁。

这样计算整个map的size的消耗就比较大了，先按乐观的情况把各个Segment的country进行合计，同时看这个过程中是否有其他线程在进行修改操作，如果有，得依次把所有Segments都锁上，然后得到各个Segment的count后再依次解开各个Segment的锁.
要我说也没必要那么accurate,因为即使返回的size是accurate，但也许下一秒又变了，得到size值的代码如果想用原来那个size进行什么计算根本就是有问题的，应该要有概念这个size随时在变的，不要想非常准确，只是一个大概准确的数字就好了。

为了确保读操作能够看到最新的值，将value设置成volatile，这避免了加锁。
volatile,据说是变量会放到主存中，不是在工作内存，达到变量共享。
（相当于全局变量？）
这里还有 volatile这个关键字的含义的问题留着。


转：”按照 JLS 的说法，"在没有显式同步的情况下，一个实现可以自由地更新主存，更新时所采取的顺序可能是出人意料的。"
其意思是说，如果没有同步的话，在一个给定线程中某种顺序的写操作对于另外一个不同的线程来说可能呈现出不同的顺序， 并且对内存变量的更新从一个线程传播到另外一个线程的时间是不可预测的。
同步提供三个独立的功能――原子性、可见性和顺序性。“

参见:
http://www.iteye.com/topic/344876
http://www.iteye.com/topic/333669

5.
in Hashtable,ConcurrentHashMap： key 和value都不可为null
in HashMap, 对key，null 用new Object()来代替，其Entry.hashCode=0,而且在取出的时候还会还回null的。

6.在Hashtable中看inner class
outer class中有个变量，在inner class中需要而且因为是相同的可以直接使用，但为了在inner class中引用outer class是不好的
宁愿重复放一个拷贝属性在inner class中，avoid needing links to outer object.

7.小技巧
对于下面的定义
private <T> Enumeration<T> getEnumeration(int type) {
  if (count == 0) {
    return (Enumeration<T>)emptyEnumerator;    //这里可以看到EmptyEnumerator的用处了
  } else {
    return new Enumerator<T>(type, false);
  }
}
用这种方式调用
this.<K>getEnumeration(KEYS);

一个静态方法来构造一个同步的Set
Collections.synchronizedSet(new KeySet(), this);

评论

5 楼 dotjar 2014-11-13  

dotjar 写道

http://burtleburtle.net/bob/hash/evahash.html
http://wangjunle23.blog.163.com/blog/static/11783817120138863910800/

mooncui 写道

haoooooj 写道

2年零3个月后，偶然路经此处，作答：

static int hash(Object x) {
        int h = x.hashCode();

        h += ~(h << 9);
        h ^=  (h >>> 14);
        h +=  (h << 4);
        h ^=  (h >>> 10);
        return h;
    }//谁能告诉我这里怎么理解？这个算法？


将10进制转换成2进制进行位移，取反，异或，运算，最后得到的是该对象的hash值。

兄台，我问的是算法，不是符号。

4 楼 dotjar 2014-11-13  

http://burtleburtle.net/bob/hash/evahash.html

mooncui 写道

haoooooj 写道

2年零3个月后，偶然路经此处，作答：

static int hash(Object x) {
        int h = x.hashCode();

        h += ~(h << 9);
        h ^=  (h >>> 14);
        h +=  (h << 4);
        h ^=  (h >>> 10);
        return h;
    }//谁能告诉我这里怎么理解？这个算法？


将10进制转换成2进制进行位移，取反，异或，运算，最后得到的是该对象的hash值。

兄台，我问的是算法，不是符号。

3 楼 ldw1986hf123 2013-12-03  

[u][/u]

2 楼 mooncui 2011-08-29  

haoooooj 写道

2年零3个月后，偶然路经此处，作答：

static int hash(Object x) {
        int h = x.hashCode();

        h += ~(h << 9);
        h ^=  (h >>> 14);
        h +=  (h << 4);
        h ^=  (h >>> 10);
        return h;
    }//谁能告诉我这里怎么理解？这个算法？


将10进制转换成2进制进行位移，取反，异或，运算，最后得到的是该对象的hash值。

兄台，我问的是算法，不是符号。

1 楼 haoooooj 2011-08-10  

2年零3个月后，偶然路经此处，作答：

static int hash(Object x) {
        int h = x.hashCode();

        h += ~(h << 9);
        h ^=  (h >>> 14);
        h +=  (h << 4);
        h ^=  (h >>> 10);
        return h;
    }//谁能告诉我这里怎么理解？这个算法？


将10进制转换成2进制进行位移，取反，异或，运算，最后得到的是该对象的hash值。