说一说java里面的hashcode–Object.hashcode()

说说java里面的hashcode--HashMap为什么用2的指数做capacity以及HashMap里面对hashcode的二次hash
http://www.hetaoblog.com/%E8%AF%B4%E8%AF%B4java%E9%87%8C%E9%9D%A2%E7%9A%84hashcode-hashmap%E4%B8%BA%E4%BB%80%E4%B9%88%E7%94%A82%E7%9A%84%E6%8C%87%E6%95%B0%E4%BB%A5%E5%8F%8Ahashmap%E9%87%8C%E9%9D%A2%E5%AF%B9hashcode%E7%9A%84/
前面一篇说了HashMap里面用2的指数做capacity，以及在此基础上的一些代码，比如IndexFor等，
而传统数据结构书上的说法是建议使用质数作为capacity,而使用2的指数作为capacity甚至被认为是最差的方式；因为哈希表的最佳情况是没有碰撞，也就是最后分布到hash数组里面尽可能均匀；

建议使用质数的原因，在SO的这里有详细的说明
http://stackoverflow.com/questions/1145217/why-should-hash-functions-use-a-prime-number-modulus
通常的哈希表是直接根据hash值对capacity取余，
而很多哈希函数的设计是和我前面文章里面提的String.hashcode()的算法类似，如果其中使用的也不是质数，那么对于一些常见的组合，比如首字母全部相同的一系列字符串，碰撞的概率极大，很可能出现所有的hash值都落在数组中的同一个位置；而使用了质数后，即使hash函数本身设计的不是很好，也很可能使得分布较为均匀；

一个简单的例子，jdk里面另外一个类,Hashtable，里面默认的capacity是11，是一个质数，并且每次resize也不是前面说的size*2， 而是size*2+1, 其目的也是尽可能保证resize后也是质数，
比如http://www.concentric.net/~ttwang/tech/hashsize.htm这里也提到如何选择hashtable的capacity, 使得几次resize以后还是质数，作者得出的结论是89是一个非常理想的数字；

但为什么HashMap使用了2的指数作为capacity呢？下面这篇文章解释了具体的原因;
http://www.javaspecialists.eu/archive/Issue054.html

居然是因为整数取余在jdk1.4.0起太慢了？！！
有人当时对这个整数计算性能下降的问题报了个bug
http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4631373
所以HashMap里面用了前面文章里面说的indexFor的按位操作函数来代替直接取余！
所以HashMap里面还加了一个二次hash(代码如下)对传入的hashcode进行二次处理，主要功能是对hashcode的低位做多次处理，使得低位也是有效的而不是在取余的过程中直接被忽略

    static int hash(int h) {
        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

就这个二次hash的函数，在1.4.0里面还有个bug，对某些哈希值会导致分布非常不均匀，碰撞非常厉害，导致性能下降非常严重
http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4669519

下面是jdk collection api的主要设计者对二次hash函数的一段说明
Joshua Bloch: The downside of using a power-of-two is that the resulting hash table is very sensitive to the quality of the hash function (hashCode). It is imperative that any change in the input must affect the low order bits of the hash value. (Ideally, it should affect all bits of the hash value with equal likelihood.) Because we have no assurance that this is true, we put in a secondary (or “defensive”) hash function when we switched to the power-of-two hash table. This hash function is applied to the results of hashCode before masking off the low order bits. Its job is to scatter the information over all the bits, and in particular, into the low order bits. Of course it has to run *very* fast, or you lose the benefit of switching to the power-of-two-sized table. The original secondary hash function in 1.4 turned out to be insufficient. We knew that this was a theoretical possibility, but we thought that it didn’t affect any practical data sets. We were wrong. The replacement secondary hash function (which I developed with the aid of a computer) has strong statistical properties that pretty much guarantee good bucket distribution

哦，这个我刚才给我的那段测试代码加了个-Xloggc:d:/mygc.log重新跑了下，发现循环设10000的时候没有gc，同时仍然有2组hash冲突，证明没有发生gc，对象地址不可能重用，所以必然不是地址；

同时，我加了你说的-XX:hashCode=4参数再跑了十几次，都没有出现一次冲突的情况；

话说证明是地址可能需要看openjdk的代码，证明不是地址，如果我上面的推理没问题的话，那段代码和结果来证明应该是没问题的，对巴？

嗯，从证伪的角度看这个做法是合理的。

说说java里面的hashcode9--关于Hashtable以及和HashMap的比较
http://www.hetaoblog.com/%E8%AF%B4%E8%AF%B4java%E9%87%8C%E9%9D%A2%E7%9A%84hashcode9-%E5%85%B3%E4%BA%8Ehashtable%E4%BB%A5%E5%8F%8A%E5%92%8Chashmap%E7%9A%84%E6%AF%94%E8%BE%83/
之前说了基本的hashcode函数，String类的实现，在hashmap里面的应用等，现在看下另外一个常用的类Hashtable,
Hashtable在jdk1.0里面就有了，而HashMap在jdk1.2里面开始有，

打开Hashtable的代码可以看到基本数据结构和Hashmap是类似的，

主要的区别是

1. Hashtable是线程安全的；
Hashtable的大部分读写方法都加了synchronized关键字,比如下面的代码

public synchronized V put(K key, V value)
public synchronized V get(Object key) {
public synchronized int size() {
public synchronized boolean isEmpty() {
public synchronized Enumeration keys() {
public synchronized boolean contains(Object value) {
public synchronized Enumeration elements() {
public synchronized boolean containsKey(Object key) {
public synchronized void clear() {

2. Hashtable既不允许null的key，也不允许null的value， 而hashmap两个都允许
下面是hashtable的put函数，可以看到无论key还是value是null都会失败

    public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) {
    throw new NullPointerException();
}

// Makes sure the key is not already in the hashtable.
Entry tab[] = table;
int hash = key.hashCode();

而HashMap里面有对null的处理，null的key总放在数组的第一个;
下面的代码对Hashtable的两个test case都会fail，而HashMap的两个test case都pass

@Test
public void testHtNullValue()
{
Hashtable ht = new Hashtable();

ht.put("", null);
}

@Test
public void testHtNullKey()
{
Hashtable ht = new Hashtable();

ht.put(null, 1);

}

@Test
public void testHmNullValue()
{
HashMap hm = new HashMap();

hm.put("", null);
}

@Test
public void testHmNullKey()
{
HashMap hm = new HashMap();

hm.put(null, 1);

}

3. 在现有的HashMap和Hashtable实现里面， 如果自己传入capacity, HashMap相对不容易有hash冲突； 因为无论传入什么值，HashMap都采用了2的指数做capacity，并且对hash值做了二次hash以后，已经是一个比较好的算法，基本能保证分布比较均匀； 而且该过程完全不受resize影响；因为Hashmap的resize就是size*2
但是Hashtable直接采用传入的值做capacity, 假设不是传入一个质数，那么对key对象的hashcode函数实现有一定的要求，如果实现的不好的话，
碰撞的概率会高一点， 而且Hashtable的2*size+1的算法在resize的过程中也会受到一定的影响，也许有可能导致分布不那么均匀，有碰撞
下面这段是Hashtable的构造函数

    public Hashtable(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
    throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal Load: "+loadFactor);

        if (initialCapacity==0)
            initialCapacity = 1;
this.loadFactor = loadFactor;
table = new Entry[initialCapacity];
threshold = (int)(initialCapacity * loadFactor);
    }

R神，能解释下open jdk默认的伪随机数算法的大概么？

http://hg.openjdk.java.net/hsx/hotspot-main/hotspot/file/694fd3171eb0/src/share/vm/runtime/os.cpp 671行

说一说java里面的hashcode10--ConcurrentHashMap代码分析
http://www.hetaoblog.com/%E8%AF%B4%E4%B8%80%E8%AF%B4java%E9%87%8C%E9%9D%A2%E7%9A%84hashcode10-concurrenthashmap%E4%BB%A3%E7%A0%81%E5%88%86%E6%9E%90/

之前说了HashMap和Hashtable的基本代码，现在看下另外一个多线程安全的Map实现类，ConcurrentHashMap,
下面是jdk对这个类的说明
A hash table supporting full concurrency of retrievals and adjustable expected concurrency for updates. This class obeys the same functional specification as Hashtable, and includes versions of methods corresponding to each method of Hashtable. However, even though all operations are thread-safe, retrieval operations do not entail locking, and there is not any support for locking the entire table in a way that prevents all access. This class is fully interoperable with Hashtable in programs that rely on its thread safety but not on its synchronization details.
这意思是说这是一个java的哈希表实现，支持完整的并发操作，包括读取和更新； 这个类实现了所有的hashtable里面的操作方法；并且，尽管这个类是线程安全的，读取操作并不一定会有锁； 而且ConcurrentHashMap并没有支持对整个类上锁，并阻止其他操作的方法；
ConcurrentHashMap可以和Hashtable完全替代，并且不依赖于Hashtable里面的synchronized方法；

下面首先看这个类里面最重要的成员变量， 一个Segment的数组
final Segment[] segments;

这个类是ConcurrentHashMap整体设计思路的核心， 这个类的代码注释第一句话是Segments are specialized versions of hash tables
也就是说每个Segment其实是一个完整的哈希表实现，

ConcurrentHashMap内部首先放一个Segment数组的作用是，对不同hash值分不同的segment，提高并发度； 真正的并发保护，也就是上锁的过程，是在segment内部的函数中完成的， 但是如果两个线程的操作对应的hash值，分布到不同的segment，那么就可以完全不受影响；

简单举例，假设一个hash值对应到segments数组的第1个，另外一个hash值最后对应到数组的第二个，那么，即使两个线程对这两个对象都有put操作，也完全可以同时进行，不会互相影响；

而Hashtable就不能做到这一点， Hashtable的synchronized关键字加在非静态方法上，其作用是加在这个具体的Hashtable对象上，那么两个线程对同一个 Hashtable对象的操作，就需要等待这个对象锁，必须串行化一个一个来，无法并发进行。

谢谢!

说一说java里面的hashcode11–ConcurrentHashMap代码分析2
http://www.hetaoblog.com/%E8%AF%B4%E4%B8%80%E8%AF%B4java%E9%87%8C%E9%9D%A2%E7%9A%84hashcode11%E2%80%93concurrenthashmap%E4%BB%A3%E7%A0%81%E5%88%86%E6%9E%902/
前面的文章说了ConcurrentHashMap的核心是通过segment对不同hash值分不同的段，上锁过程在每个段内部完成；
下面看下这个Segment类的基本代码

static final class Segment extends ReentrantLock

首先，每个Segment类都继承了ReentrantLock，这样做是方便调用lock和unlock操作，省得额外声明一个成员变量做lock;
接下来看到成员变量，基本和一个普通的HashMap类似，所以说每个Segment都是一个完整的Hashtable

transient volatile int count;
transient int modCount;
transient int threshold;
transient volatile HashEntry[] table;
final float loadFactor;

接下来看下Segment的put和get函数， 先看下比较简单的get函数, count是一个volatile的计数器，保存了这个Segment里面元素的个数，
getFirst函数就是先根据hash值取在table上的index，然后取第一个，取到数组上的元素后，就开始对这个链表进行遍历，取到了就返回；
其中有可能会是null的情况，需要加锁访问，这个readValueUnderLock函数的注释是说仅仅在java编译器对HashEntry的初始化做re-order的时候才可能发生，这在java的内存模型中是可能的，但是在运行到这句之前是无法预知的；
// 这种reorder，在著名的double checked singleton 模式中，也有影响， 我个人反对把简单的singleton用复杂的，极有可能出错的方式来实现

可以看到，即使是在一个segment上的get操作，在多线程环境中，大部分情况也是不需要上锁的；

        V get(Object key, int hash) {
            if (count != 0) { // read-volatile
                HashEntry e = getFirst(hash);
                while (e != null) {
                    if (e.hash == hash && key.equals(e.key)) {
                        V v = e.value;
                        if (v != null)
                            return v;
                        return readValueUnderLock(e); // recheck
                    }
                    e = e.next;
                }
            }
            return null;
        }

下面看下put函数的代码

       V put(K key, int hash, V value, boolean onlyIfAbsent) {
            lock();
            try {
                int c = count;
                if (c++ > threshold) // ensure capacity
                    rehash();
                HashEntry[] tab = table;
                int index = hash & (tab.length - 1);
                HashEntry first = tab[index];
                HashEntry e = first;
                while (e != null && (e.hash != hash || !key.equals(e.key)))
                    e = e.next;

                V oldValue;
                if (e != null) {
                    oldValue = e.value;
                    if (!onlyIfAbsent)
                        e.value = value;
                }
                else {
                    oldValue = null;
                    ++modCount;
                    tab[index] = new HashEntry(key, hash, first, value);
                    count = c; // write-volatile
                }
                return oldValue;
            } finally {
                unlock();
            }
        }

可以看到，put操作，需要对整个segment上锁，如果看过我这个系列的文章，这里不难理解，基本就是在保证容量的情况下，找到数组中的元素，然后对这个链表进行遍历，如果存在的话就更新，如果不存在的话就添加；

再看下其他的函数，比如containsKey/containsValue等函数，可以看到这些读取函数都是没有上锁的；

        boolean containsKey(Object key, int hash) {
            if (count != 0) { // read-volatile
                HashEntry e = getFirst(hash);
                while (e != null) {
                    if (e.hash == hash && key.equals(e.key))
                        return true;
                    e = e.next;
                }
            }
            return false;
        }

        boolean containsValue(Object value) {
            if (count != 0) { // read-volatile
                HashEntry[] tab = table;
                int len = tab.length;
                for (int i = 0 ; i < len; i++) {
                    for (HashEntry e = tab[i]; e != null; e = e.next) {
                        V v = e.value;
                        if (v == null) // recheck
                            v = readValueUnderLock(e);
                        if (value.equals(v))
                            return true;
                    }
                }
            }
            return false;
        }

而像replace,clear这些写入函数，是需要对该segment上锁的

        V replace(K key, int hash, V newValue) {
            lock();
            try {
                HashEntry e = getFirst(hash);
                while (e != null && (e.hash != hash || !key.equals(e.key)))
                    e = e.next;

                V oldValue = null;
                if (e != null) {
                    oldValue = e.value;
                    e.value = newValue;
                }
                return oldValue;
            } finally {
                unlock();
            }
        }
        void clear() {
            if (count != 0) {
                lock();
                try {
                    HashEntry[] tab = table;
                    for (int i = 0; i < tab.length ; i++)
                        tab[i] = null;
                    ++modCount;
                    count = 0; // write-volatile
                } finally {
                    unlock();
                }
            }
        }

当然，这些操作都是在Segment层面上的，对应到ConcurrentHashMap这个类上，未必完全对应；
ConcurrentHashMap的get/containskey函数，基本可以看作是简单的对应，所以仍然是没有上锁的

   public V get(Object key) {
        int hash = hash(key.hashCode());
        return segmentFor(hash).get(key, hash);
    }
    public boolean containsKey(Object key) {
        int hash = hash(key.hashCode());
        return segmentFor(hash).containsKey(key, hash);
    }

但是containsValue操作比较复杂，先尝试几次后，如果没有得出结论，在最后有可能会有一个对所有segment上锁并全部解锁的过程,

   public boolean containsValue(Object value) {
        if (value == null)
            throw new NullPointerException();

        // See explanation of modCount use above

        final Segment[] segments = this.segments;
        int[] mc = new int[segments.length];

        // Try a few times without locking
        for (int k = 0; k < RETRIES_BEFORE_LOCK; ++k) {
            int sum = 0;
            int mcsum = 0;
            for (int i = 0; i < segments.length; ++i) {
                int c = segments[i].count;
                mcsum += mc[i] = segments[i].modCount;
                if (segments[i].containsValue(value))
                    return true;
            }
            boolean cleanSweep = true;
            if (mcsum != 0) {
                for (int i = 0; i < segments.length; ++i) {
                    int c = segments[i].count;
                    if (mc[i] != segments[i].modCount) {
                        cleanSweep = false;
                        break;
                    }
                }
            }
            if (cleanSweep)
                return false;
        }
        // Resort to locking all segments
        for (int i = 0; i < segments.length; ++i)
            segments[i].lock();
        boolean found = false;
        try {
            for (int i = 0; i < segments.length; ++i) {
                if (segments[i].containsValue(value)) {
                    found = true;
                    break;
                }
            }
        } finally {
            for (int i = 0; i < segments.length; ++i)
                segments[i].unlock();
        }
        return found;
    }

我基本理解是containsValue这个函数可能要慎重使用，有可能会因为最后的全部加锁过程导致在并发情况下性能比较差；

说一说java里面的hashcode12–关于LinkedHashMap
http://www.hetaoblog.com/%E8%AF%B4%E4%B8%80%E8%AF%B4java%E9%87%8C%E9%9D%A2%E7%9A%84hashcode12%E2%80%93%E5%85%B3%E4%BA%8Elinkedhashmap/
jdk里面Map的实现有一个略有点意思，就是LinkedHashMap,
我们知道，HashMap本身是没有顺序的，TreeMap是按照key有顺序的， 其中HashMap有个子类，也是有顺序的，这个顺序和TreeMap的顺序略有不同，LinkedHashMap是按照插入的顺序来的，下面是一段测试代码和打印结果:

@Test
public void testHashMap()
{

HashMap hm = new HashMap();
System.out.println(hm.getClass());
testOrder(hm);

LinkedHashMap lhm = new LinkedHashMap();
System.out.println(lhm.getClass());
testOrder(lhm);

TreeMap tm = new TreeMap();
System.out.println(tm.getClass());
testOrder(tm);

}

public void testOrder(Map m)
{
//

for(int i = 10; i > 0; --i)
{
m.put("" + i, i);
}

for(int i = 11; i < 20; ++i)
{
m.put("" + i, i);
}

for(String s: m.keySet())
{
System.out.println(s + ": " + m.get(s));
}

}

打印结果是:

class java.util.HashMap
19: 19
17: 17
18: 18
15: 15
16: 16
13: 13
14: 14
11: 11
12: 12
3: 3
2: 2
10: 10
1: 1
7: 7
6: 6
5: 5
4: 4
9: 9
8: 8
class java.util.LinkedHashMap
10: 10
9: 9
8: 8
7: 7
6: 6
5: 5
4: 4
3: 3
2: 2
1: 1
11: 11
12: 12
13: 13
14: 14
15: 15
16: 16
17: 17
18: 18
19: 19
class java.util.TreeMap
1: 1
10: 10
11: 11
12: 12
13: 13
14: 14
15: 15
16: 16
17: 17
18: 18
19: 19
2: 2
3: 3
4: 4
5: 5
6: 6
7: 7
8: 8
9: 9

可以看到HashMap毫无顺序，TreeMap安装key的顺序比较来（注意到这里字符串比较"11"会排在"2"的前面）， 而LinkedHashMap是按照插入的顺序来；