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

http://www.hetaoblog.com/%E8%AF%B4%E4%B8%80%E8%AF%B4java%E9%87%8C%E9%9D%A2%E7%9A%84hashcode-object-hashcode/
java里面Object这个类的方法里面，一个重要的方法是hashcode(), 下面是javadoc
public int hashCode()
Returns a hash code value for the object. This method is supported for the benefit of hashtables such as those provided by java.util.Hashtable.
The general contract of hashCode is:

Whenever it is invoked on the same object more than once during an execution of a Java application, the hashCode method must consistently return the same integer, provided no information used in equals comparisons on the object is modified. This integer need not remain consistent from one execution of an application to another execution of the same application.
If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must produce the same integer result.
It is not required that if two objects are unequal according to the equals(java.lang.Object) method, then calling the hashCode method on each of the two objects must produce distinct integer results. However, the programmer should be aware that producing distinct integer results for unequal objects may improve the performance of hashtables.
As much as is reasonably practical, the hashCode method defined by class Object does return distinct integers for distinct objects. (This is typically implemented by converting the internal address of the object into an integer, but this implementation technique is not required by the JavaTM programming language.)

Returns:
a hash code value for this object.

这段话说了关于hashcode()这个函数的几个意思:
1. 用在Hashtable这个类， 其实其他还有HashMap, HashSet, ConcurrentHashMap等类上，一般类名里面有Hash字样的集合类，基本都要用到hashcode()这个函数
2. 同一个对象，如果用来在equals判断的属性未发生改变，那么在同一个进程里面hashcode()函数的多次调用，始终应该返回同一个整数
3. 如果两个对象用equals方法判断为相同，那么hashcode()也应该返回同样的值； 否则hashtable/hashmap这些类就不能正常工作了
4. 如果两个对象用equals方法判断为不同，hashcode可以一样， 就是所谓的hashcode()冲突； 虽然hashcode()可能冲突，但是冲突会使得hashtable()/hashmap()效率下降，我们在自己重写hashcode()函数的时候需要尽可能的让冲突减少； 事实上，很多情况下hashcode()的冲突是难以避免的；
5. jdk的javadoc说’As much as is reasonably practical’, Object.hashcode()会返回不同的值， 通常是返回对象的内存地址；
但是实际上，我在hotspot jdk 1.6.30/winxp下面测试，发现并没有返回对象的地址，并且的确是有冲突的，下面是测试代码和运行结果,

   for(int i = 0; i < 10000; ++i)
        {
            Object o = new Object();
            os.add(o);
            Integer h = o.hashCode();

            if((i == 361) || (i == 1886) || (i == 2185) || (i == 1905))
            {
                System.out.println("i,hashcode(): " + i + "," + h);
            }

            if(s.contains(h))
            {
                System.out.println("conflict:" + i + ", " + m.get(h));
            }
            else
            {
                s.add(h);  
                m.put(h,  i);
            }

        }

        System.out.println(s.size());

        int c = 0;
        for(Object o: os)
        {
            c++;
        }

        System.out.println(c);
    }

我运行了两次，结果分别是
i,hashcode(): 361,9578500
i,hashcode(): 1886,9578500
conflict:1886, 361
i,hashcode(): 1905,14850080
i,hashcode(): 2185,14850080
conflict:2185, 1905
9998
和

i,hashcode(): 361,5462872
i,hashcode(): 1886,29705835
conflict:1887, 362
i,hashcode(): 1905,9949222
i,hashcode(): 2185,2081190
conflict:2186, 1906
9998
10000

说明：
1. 代码最后的 for(Object o: os)里面对count统计出10000，表示所有对象都没有被回收，也就不可能存在同一个地址被两次分配空间的情况
2. 在这个10000的循环中，每次都有两组对象发生冲突，说明在这个版本的jdk里面，Object.hashcode()肯定没有返回对象的地址；
2. 在这个10000的循环中，每次都有两组对象发生冲突，说明在这个版本的jdk里

//这几天都看这个，准备拿这个贴盖楼
2. 说一说java里面的hashcode()—String.hashcode()
http://www.hetaoblog.com/%E8%AF%B4%E4%B8%80%E8%AF%B4java%E9%87%8C%E9%9D%A2%E7%9A%84hashcode-string-hashcode/
前一篇文章说了Object.hashcode(),现在来看下String.hashcode(), 因为很多情况下HashMap和HashTable的key是String；
下面是jdk里面的代码和注释

Returns a hash code for this string. The hash code for a String object is computed as
s[0]*31^(n-1) + s[1]*31^(n-2) + … + s[n-1]

using int arithmetic, where s[i] is the ith character of the string, n is the length of the string, and ^ indicates exponentiation. (The hash value of the empty string is zero.)

public int hashCode() {
int h = hash;
int len = count;
if (h == 0 && len > 0) {
int off = offset;
char val[] = value;

for (int i = 0; i < len; i++) {
h = 31*h + val[off++];
}
hash = h;
}
return h;
}

这个意思是说

1. String.Hashcode()的算法是s[0]*31^(n-1) + s[1]*31^(n-2) + … + s[n-1],就是每个字符的ascii值以质数31作为进制计算后得到的结果就是，相当于31进制；

实际的计算过程是从左向右计算，每移一位对之前算的值乘以31

2. 同时，有个成员变量hash保存了计算过的hashcode()， 第一次调用String.hashcode() 后，计算出来的hashcode()就保存在hash成员变量中，以后就直接返回了；  当然，这里有个特殊的地方是String是常量，就是创建以后值就不再变了， “Strings are constant; their values cannot be changed after they are created.”, 这是jdk里面的说明;所以他的hashcode()也永远不会变化，可以缓存在成员变量里面

3. 既然String.hashcode()的算法已经明确了，那么就可以尝试构造冲突，

假设两个字符串都是有两个字符，那么如果满足 a1*31+b1 = a2*31 +b2这个等式，这两个字符串的hashcode()就一样

也就是(a1-a2)*31=b2-b1 ，如果设a1-a2=1, 那么b2-b1=31就好， ascii表里面满足这个等式的字符串可以找出很多来, 下面是一段测试代码

public void testHash()

{

    System.out.println("A:" + (int)'A');

    System.out.println("B:" + (int)'B');

    System.out.println("a:" + (int)'a');

    System.out.println("Aa".hashCode() + "," + "BB".hashCode());

    System.out.println("Ba".hashCode() + "," + "CB".hashCode());

    System.out.println("Ca".hashCode() + "," + "DB".hashCode());

    System.out.println("Da".hashCode() + "," + "EB".hashCode());

}

打印的结果

A:65

B:66

a:97

2112,2112

2143,2143

2174,2174

2205,2205

可以看到，这些字符串都满足上面的等式，都发生了hashcode()冲突的情况； 并且，只要按照上面的方法，可以构造出很多两个字符串的冲突来；

更进一步，假设两个字符串都有4个字符串，按照公式，假设前两个字符串产生hashcode为m, 后两个字符串产生hashcode为n,

那么，4个字符串的hashcode是m*31^2+n, 所以，如果两个字符串组成的hashcode()是一样的，那么4个字符串组成的hashcode也是一样的！

所以，”AaAa”, “BBBB”,”AaBB”,”BBAa”的hashcode都一样，都是2031744，

而”CaDB”,”CaCa”,”DBCa”,”DBDB”的hashcode都一样，是2091388；

并且按照这个方法，可以构造6个字符串，8个字符串等hashcode相同的字符串来；

去年的hash冲突导致dos攻击的漏洞，基本就可以按照这个方法构造错误

酷壳的Hash Collision DoS 问题里面也详细说明了当时的情况，不过陈浩举例的hash函数其实是HashMap的hash函数，

那个其实是对已经产生的hashcode()做二次hash，并不是String.hashcode()的代码，

可能读者看那个代码和后续的说明不能直接看明白为什么Aa和BB的hash值是一样的，也不知道为什么进一步可以得出AaBB和AaAa的hash值也一样的

相信读者看了这篇文章应该会清楚了

当然，陈浩的技术很好,我一直都很喜欢看他的文章

说一说java里面的hashcode3-再说string-hashcode
http://www.hetaoblog.com/%E8%AF%B4%E4%B8%80%E8%AF%B4java%E9%87%8C%E9%9D%A2%E7%9A%84hashcode3-%E5%86%8D%E8%AF%B4string-hashcode/

前一篇文章说一说java里面的hashcode-string-hashcode， 这篇再多说一下这个String.hashcode(),

我看到String.hashcode()的冲突的时候，第一个想法就是，哈，那不是质数31取的太小了么？导致在常用ascii字符集里面容易冲突，那么，直接设个大点的质数不就好了么？幸运的是，257就是个质数，那么就用257，立刻就可以避免之前的冲突的例子了，下面是一段代码

@Test
public void testBetterhash()
{
    System.out.println(betterHash("Aa") + "," + betterHash("BB"));
    System.out.println(betterHash("Ba") + "," + betterHash("CB"));
    System.out.println(betterHash("Ca") + "," + betterHash("DB"));
    System.out.println(betterHash("Da") + "," + betterHash("EB"));
}
public static int betterHash(String s)
{
    int h = 0;
    int len = s.length();

    for (int i = 0; i < len; i++) {
        h = 257*h + s.charAt(i);
    }

    return h;
}

返回的结果很好，全部不冲突
16802,17028
17059,17285
17316,17542
17573,17799

不过悲剧的是，该算法相当于以257为进制，每次乘以257至少相当于移了8位多，在32位jdk下面，int只有32位，遇到5个字符就溢出了，调用betterHash("abcde")就会返回-372058641

所以，这个想法自然就失败了；
那么，原来的String.hashcode()算法在‘通常情况’下大约有多少的冲突概率呢？

为此，我从http://www.mieliestronk.com/wordlist.html下载了常用英文单词表，其中包含了将近6万个单词，我为了测试大小写排列组合的情况，取了前面5000个单词，然后对每个单词做大小写全排列，
也就是cat会有cat/caT/cAt/cAT/Cat/CaT/CAt/CAT 这8种情况，得到8021600个不同的字符串，分别计算他们的hashcode(),得到了8012142个不同的hashcode，也就是有9458 个冲突，在这样的场景下，大约有超过千分之一的冲突；

我想, jdk的实现肯定是经过了充分的考虑，考虑到大多数情况下能够在所有域上冲突能够做均匀分布；

说一说java里面的hashcode4-hashmap代码分析1

http://www.hetaoblog.com/%E8%AF%B4%E4%B8%80%E8%AF%B4java%E9%87%8C%E9%9D%A2%E7%9A%84hashcode4-hashmap%E4%BB%A3%E7%A0%81%E5%88%86%E6%9E%901/
现在进入hashcode第4篇，HashMap代码分析，
先看到这个类的成员变量，有下面8个，
static final int DEFAULT_INITIAL_CAPACITY = 16; // 默认的容量
static final int MAXIMUM_CAPACITY = 1 << 30; // 最大容量， 取到2^30
static final float DEFAULT_LOAD_FACTOR = 0.75f; // 默认的load factor,
transient Entry[] table; // 这里，用一个数组存储了真正的Entry，Entry里面有成员k和v
transient int size; // 大小
int threshold; // 容量限制
final float loadFactor; // 实际load factor
transient volatile int modCount;

重点:
* 实际的kv数据用一个entry类，存放在一个数组里面
下面看下默认的构造函数

    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
        table = new Entry[DEFAULT_INITIAL_CAPACITY]; // 构造Entry表格
        init(); // 这个函数是空的，可以忽略
    }

下面是put函数，这段函数的主要意思:
1. 因为HashMap允许null(而HashTable不允许), 所以如果是null的话先固定放到第一个
2. 对对象的hashcode()再做一次hash，然后取索引，这里略有点故事，一般hash表的数组长度应该是质数，而jdk里面的HashMap选了2的指数作为数组大小，这里要做一次保护，这个下次可以单独写一点
3. 接下来，取到这个哈希数组里面的索引这项，然后对这项上的链表进行遍历，看看有没有存在一个key，和新放进来的元素hash值一样，并且（是同一个元素或者equals方法也返回相等）(这就是为什么Object.hashcode()里面会有那样的约定，如果你违法了那边的约定，假设两个对象 equals返回true，本质上是同一个对象，但是hashcode不一样的话，那两次put会放到两个不同的地方了；
如果有的话，说明是同一个key对象，用新的value替换老的value，并且返回老的value
4. 如果不存在同一个key，那么就把该元素加入到这个哈希数组的这个位置(就是通过hashcode()再做hash，然后取索引的这项)

    public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key.hashCode());
        int i = indexFor(hash, table.length);
        for (Entry e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

modCount++;
addEntry(hash, key, value, i);
return null;
}

这里具体的addEntry代码如下：

    void addEntry(int hash, K key, V value, int bucketIndex) {
Entry e = table[bucketIndex];
        table[bucketIndex] = new Entry(hash, key, value, e);
        if (size++ >= threshold)
            resize(2 * table.length);
    }

以及Entry的实现和构造函数:

    static class Entry implements Map.Entry {
        final K key;
        V value;
        Entry next;
        final int hash;

        /**
         * Creates new entry.
         */
        Entry(int h, K k, V v, Entry n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }

可以看到，
1. 新添加的元素被放到了哈希数组这个位置上面的链表的第一个；
2. 如果HashMap里面存放的总的元素个数超过了threshold(也就是capacity*loadfactor)， 那么就把存放数据的数组扩大一倍
这里面是说总的元素个数，下面的代码是会打印2的。其实就是已经存了比较多的数据了，基本上直接hash一次访问到的概率比较小了，很可能很多元素都要继续通过访问后面的Entry链表来得到，效率就下降了，Hash的优势已经不那么明显了，所以把表格扩大一倍，把原来的元素根据hash值重新做一次索引和分布，尽可能让链表缩短，提高访问效率

Map m = new HashMap();

m.put("BB", 10);
m.put("Aa", 11);

System.out.println(m.size());

说一说java的hashcode5–HashMap代码分析2
http://www.hetaoblog.com/%E8%AF%B4%E4%B8%80%E8%AF%B4java%E7%9A%84hashcode5-hashmap%E4%BB%A3%E7%A0%81%E5%88%86%E6%9E%902/
前面一篇说了HashMap的大概结构和如何put, 下面是get函数的代码,

    public V get(Object key) {
        if (key == null)
            return getForNullKey();
        int hash = hash(key.hashCode());
        for (Entry e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
                return e.value;
        }
        return null;
    }

这段代码非常直接，就是传入一个key，如果是null的话，特殊处理下null的key，
然后就是通过hash(key.hashCode())二次处理hash值，再通过indexFor(hash, table.length)函数得到该hash值在哈希数组中的位置；
取到位置后，就是一个链表，对这个链表遍历，取到hash值一样，并且(key指向同一个引用或者equals返回true的key)

说一说java的hashcode6–HashMap的resize和transfer
http://www.hetaoblog.com/%E8%AF%B4%E4%B8%80%E8%AF%B4java%E7%9A%84hashcode6-hashmap%E7%9A%84resize%E5%92%8Ctransfer/

HashMap的put函数的最后一行是，
addEntry(hash, key, value, i);
说明：就是把key和value通过一个addEntry函数放到哈希数组对应位置上的链表中

addEntry的最后两行是
if (size++ >= threshold)
resize(2 * table.length);
说明：如果HashMap里面的元素的个数超过了threshold(默认是capacity*loadfactor，默认的loadfactor是0.75）， 就会触发resize函数；
resize的大小当前数组的2倍；

下面是resize函数
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}

Entry[] newTable = new Entry[newCapacity];
transfer(newTable);
table = newTable;
threshold = (int)(newCapacity * loadFactor);
}
说明：按照新的capacity(也就是当前*2）分配一个新的数组，然后通过transfer函数把老的数据拷贝到新的数组里面，然后将table指向newtable,重新计算threshold,

其中调用了transfer函数
void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) {
Entry e = src[j];
if (e != null) {
src[j] = null;
do {
Entry next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}
}
transfer 函数本质上就是把就的table里面的东西放到newtable里面， 这里我们可以注意到：
1. 因为数组大小扩大了一倍，所以对应同一个hash值，其在数组中的index已经发生了变化,需要重新计算index,
2. 数组同一个链表上的元素的hash值并不相同，他们只是对数组长度取余的结果相同，比如原来数组长度是16，那么，hash值是15和31的元素都会落在数组的第15个位置[以0为基数]，就是最后一个位置，
所以，对应数组同一个位置上链表里面的每一个元素，其hash值都有可能不一样，重新index到新的数组里面的位置也可能不一样，比如上面说的15和31就会分别到15和31
3. 由于链表上面可能有多个元素，并且老的链表上面的元素放到新的链表上的位置都有可能不一样了，
所以，对老链表的每个元素，在计算新的index的时候，每次都把老链表上的元素放在新链表的最开始的第一个，避免对新链表的遍历；

其实楼主真的有试过看那个值是不是“地址”么？…

Object.hashCode()在没有被override的地方返回的是该对象的identity hash code。被override过hashCode()的对象也可以通过System.identityHashCode()来获取该值。
实际上HotSpot VM默认是不使用地址作为Java对象的identity hash code的。默认用的是一个伪随机数生成器。

也有办法让HotSpot VM使用对象的identity hash code被访问时的地址。请看例子：https://gist.github.com/1588977

说一说java里面的hashcode--HashMap里面的indexFor函数
http://www.hetaoblog.com/%E8%AF%B4%E4%B8%80%E8%AF%B4java%E9%87%8C%E9%9D%A2%E7%9A%84hashcode-hashmap%E9%87%8C%E9%9D%A2%E7%9A%84indexfor%E5%87%BD%E6%95%B0/
indexFor函数在HashMap里面有较多的应用，从hash值得到该hash值在table里面的索引都是用这个函数，下面是代码:

    static int indexFor(int h, int length) {
        return h & (length-1);
    }

比如在get函数里面就有下面的代码

for (Entry e = table[indexFor(hash, table.length)];

上面的indexFor函数有个前提，就是length是2的指数；

下面是HashMap的默认capacity(就是length)
/**
* The default initial capacity – MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 16;

下面是HashMap构造函数的代码,这是说无论你传入的initialCapacity是多少，内部始终会给你找到第一个比你传入的Capacity大的那个2的指数
// Find a power of 2 >= initialCapacity
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;

好了，既然已经保证了capacity是2的指数，h & (length-1)这句究竟是什么意思呢？
其实结果就相当于h%length， 也就是h对length取余，只是是通过按位与的方式来实现;

举例，假设length是默认的16， 那么作为2进制就是10000, length-1就是15，对应二进制就是01111,然后和h做按位与就是取后面4位，所以结果就是取余； 比如h是17，对应二进制是10001, 和01111取余就是0001，就是1；

哇！R神啊！

这个我在第一贴里面贴了我的测试代码，取了10000个对象的hashcode()，得到了9998个不同的hashcode,其中有两个重复，并且这10000个对象都保持到后面继续使用，使得这些对象没有被垃圾回收，都存在于heap上，那么可以认为取的不是地址，因为这10000个对象都还在heap里面，如果取地址的话肯定不可能有重复。

当然：我这有一个前提，假设new 了这10000个对象没有发生GC，对象没有发生因为移动过而导致地址重用的情况；
这个我默认是这样，回头我再验证下是否真的没有发生gc；


话说我没看明白你的意思？既然你说了默认是伪随机数，那我说没有返回地址有问题么？
还是你想问我我是如何看返回的hashcode()不是地址的？

<< 是这个。虽然HotSpot VM算的identity hash code确实不是用地址，但你并没有确认它的手段。

而且上面也提到了，可以通过一个启动参数来让它返回一个跟地址相关的值。