求高手 详解 HashSet的扩容机制

Question

import java.util.*;
public class TestHashSet{
public static void main(String[] args){
HashSet hs = new HashSet();
for(int i=1;i<=20;i++){
hs.add(i);
}
System.out.println(hs);
}
}
HashSet集合是无序、唯一    默认元素个数是16，加载因子是0.75F，运行上述代码发现，第16个元素就开始无序了，这是什么原理？究竟是在什么时候扩容的？

Answer 1

不管有多少元素，HashSet都是无序的。

Answer 2

这里的有序指的是 nature order 或者Comparator定义的顺序。
这里你发现从16开始开始乱序，就是无序（其实这个顺序和元素的hash code有关）；而每次打出来顺序相同不能说明每次都是有序的，也就是说每次排错队的顺序一样而已。如果真要有序set可以用TreeSet。

Answer 3

http://blog.csdn.net/michaellufhl/archive/2010/08/23/5833188.aspx

Answer 4

看 java.util.HashSet 的源码
可以看出来，其底层是基于 java.util.HashMap.相当于key和value相同的HashMap
其扩容机制也是依赖于HashMap的扩容机制
而HashMap的默认扩容机制，是存储的key超过容量的75%时，容量翻番.
ps:其实，这些和有序无序没关系
排序的具体实现，注意查看
HashMap.hash(int h)方法
及
HashMap.indexFor(int h, int length)方法

Answer 5

这是hash 实现的原理，像一般 cellection,要找一个元素，调用 get(index)  或者 get(object)  ,基本上都需要线性时间，是与 collection 的元素个数成正比的。而 hash 实现，如果冲突少的话，只需要 1个单位时间。这是hash 实现的好处，楼主应该知道 ArraList  ,他 的 get(index) 也只需要  1 个单位时间，他直接通过数组下标去访问元素，而hash 实现，则是利用 object.hashcode() ,当做他的下标，去索引元素。hash 数据结构里面有更详细的介绍。

Answer 6

Hash开头的 类，都是以Hash码来排序的，
内部实现机制 添加元素的时候 会将元素的key换算成一个hash码，并根据hash码进行排序
Link开头的 都是有序的 ，如同一条线一样的序列，

Answer 7

按道理说是达到初始容量的75% 时进行扩容，那麽就是12，但刚才在源码里面看了看，没有发现何时扩容，还有就是HashSet内部是通过HashMap实现的，add 的元素的key唯一，无序， 

Answer 8

HashMap.javaput方法：

addEntry(hash, key, value, i);
addEntry方法:
...
if (size++ >= threshold)
            resize(2 * table.length);
...如果对象个数超过容量的75%，就直接容量翻番

Answer 9

仔细看了看源码，找到了问题 public boolean add(E e) { //hashSet 的add方法，调用了 hashMap的put方法
return map.put(e, PRESENT)==null;
    }public V put(K key, V value) {//hashMap的put方法
    if (key == null)//判断key是否为空
        return putForNullKey(value);
    int hash = hash(key.hashCode());//得到key的hash值
    int i = indexFor(hash, table.length);//得到key在Hash表中的位置索引
    for (Entry<K,V> e = table[i]; e != null; e = e.next) { //for循环主要是查找表中是否有与要插入
        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;
        }
    }
    //下面的代码主要是处理 由于在hash表中没找到与要插入的对象相同的对象
    modCount++;
    addEntry(hash, key, value, i); //在Hash表中增加一个元素
    return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex]; 
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
        if (size++ >= threshold)   //扩容了
            resize(2 * table.length); //为原容量得2
倍
    }