1.Hashtable概要:实现Map接口的同步实现
  •     线程安全
  •     不能存储null到key和value
  •    HashTable中hash数组默认大小是11,增加的方式是 old*2+1。HashMap中hash数组的默认大小是16,而且一定是2的指数

    区别

    Hashtable

    Hashmap

    继承、实现

    Hashtable extends Dictionaryimplements Map, Cloneable,Serializable

    HashMap extends AbstractMap implements Map, Cloneable,Serializable

    线程同步

    已经同步过的可以安全使用

    未同步的,可以使用Colletcions进行同步Map Collections.synchronizedMap(Map m)

    对null的处理

    Hashtable table = new Hashtable();

    table.put(null, "Null");

    table.put("Null", null);

    table.contains(null);

    table.containsKey(null);

    table.containsValue(null);

    后面的5句话在编译的时候不会有异常,可在运行的时候会报空指针异常具体原因可以查看源代码

    public synchronized V put(K key, V value) {

    // Make sure the value is not null

    if (value == null) {

    throw new NullPointerException();

    }

    HashMap map = new HashMap();
    map.put(null, "Null");

    map.put("Null", null);

    map.containsKey(null);

    map.containsValue(null);

    以上这5条语句无论在编译期,还是在运行期都是没有错误的.

    在HashMap中,null可以作为键,这样的键只有一个;可以有一个或多个键所对应的值为null。当get()方法返回null值时,即可以表示 HashMap中没有该键,也可以表示该键所对应的值为null。因此,在HashMap中不能由get()方法来判断HashMap中是否存在某个键,而应该用containsKey()方法来判断。

    增长率

    protected void rehash() {

    int oldCapacity = table.length;

    Entry[] oldMap = table;

    int newCapacity = oldCapacity * 2 + 1;

    Entry[] newMap = new Entry[newCapacity];

    modCount++;

    threshold = (int)(newCapacity * loadFactor);

    table = newMap;

    for (int i = oldCapacity ; i-- > 0 ;) {

    for (Entry old = oldMap[i] ; old != null ; ) {

    Entry e = old;

    old = old.next;

    int index = (e.hash & 0x7FFFFFFF) % newCapacity;

    e.next = newMap[index];

    newMap[index] = e;

    }

    }

    }

    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);

    }

    哈希值的使用

    HashTable直接使用对象的hashCode,代码是这样的:

    public synchronized booleancontainsKey(Object key) {

    Entry tab[] = table;

    int hash = key.hashCode();

    int index = (hash & 0x7FFFFFFF) % tab.length;

    for (Entry e = tab[index] ; e !=null ; e = e.next) {

    if ((e.hash == hash) && e.key.equals(key)) {

    return true;

    }

    }

    return false;

    }

    HashMap重新计算hash值,而且用与代替求模

    public boolean containsKey(Object key) {

    Object k = maskNull(key);

    int hash = hash(k.hashCode());

    int i = indexFor(hash, table.length);

    Entry e = table[i];

    while (e != null) {

    if (e.hash == hash && eq(k, e.key))

    return true;

    e = e.next;

    }

    return false;

    }

posted @ 2012-02-21 10:32 陈睿 阅读(1060) | 评论 (0)编辑 收藏
1.  HashMap概要:基于哈希表Map接口的非同步实现
  • 线程不安全,线程安全请使用Hashtable
  • 效率较好
  • 提供null作为key或者value

2.  HashMap代码详解
  •     默认 初始化
                 /**
     * Constructs an empty <tt>HashMap</tt> with the default initial capacity
     * (16) and the default load factor (0.75).
     
*/
    
public HashMap() {
        
this.loadFactor = DEFAULT_LOAD_FACTOR;        //默认是0.75
        threshold 
= (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);//扩容的门槛,存入的数据大于该值,容量扩充一倍
        table 
= new Entry[DEFAULT_INITIAL_CAPACITY];//初始化数组,数组内容为Entry,存储链表    
        init();

  • 存入元素:
public V put(K key, V value) {
        
if (key == null)
            
return putForNullKey(value);//如果key为null,直接把value放到数组第一位table[0]
        
int hash = hash(key.hashCode());//通过可以的hashcode计算对应的hash值
        
int i = indexFor(hash, table.length);//通过hash值,把entry对应到数组的位数计算出来
        
for (Entry<K,V> e = table[i]; e != null; e = e.next) {//如果该entry还包含下一个entry的引用,则继续遍历该链表            
            Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {//如果key相同,则替换新的value到制定的key
                V oldValue 
= e.value;
                e.value 
= value;
                e.recordAccess(
this);
                
return oldValue;
            }
        }

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

  • 读取元素:
 public V get(Object key) {
        
if (key == null)//key为null,直接从数组第一位拿数据
            
return getForNullKey();
        
int hash = hash(key.hashCode());
        
for (Entry<K,V> e = table[indexFor(hash, table.length)];  //直接通过key的hashcode计算出对应到数组的索引位,直接取数据,如果有链表继续查找
             e 
!= null;
             e 
= e.next) {
            Object k;
            
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
                
return e.value;
        }
        
return null;
    }



  • 总结:
        HashMap别的方法就不继续详解了,主要通过put与get可以很好的理解HashMap底层的结构,以及工作方式。








posted @ 2012-02-20 16:40 陈睿 阅读(990) | 评论 (0)编辑 收藏
1. Vector概要:
  • 默认长度为10
                  /**
     * Constructs an empty vector so that its internal data array
     * has size {
@code 10} and its standard capacity increment is
     * zero.
     
*/
    
public Vector() {
    
this(10);
    }
  • 底层采用数组存储protected Object[] elementData;
  • 线程安全
  • 查询效率比较高,比较适用于查询
  • 扩容的长度为初始长度的一半,建议初始化的时候设置已知的长度,免得容器自己去扩容,浪费空间以及效率
    与ArrayList基本一样,除了所有操作资源的方法都加了
    synchronized,保证线程同步
    这里的源代码就不详解了,具体请参考容器-数组-ArrayList详解
posted @ 2012-02-20 16:11 陈睿 阅读(180) | 评论 (0)编辑 收藏
1. ArrayList概要:
  • 默认长度为10
                 public ArrayList() {
                this(10);
                 }
  • 底层采用数组存储private transient Object[] elementData;
        transient表示数组elementData不需要通过serialization序列化传输
  • 线程不安全,在多线程场景会出现问题,可以考虑使用Vector或者Collections.synchronizedList同步该容器
  • 查询效率比较高,比较适用于查询
  • 扩容的长度为初始长度的一半,建议初始化的时候设置已知的长度,免得容器自己去扩容,浪费空间以及效率

2. ArrayList代码详解:

  • 增加元素
  public boolean add(E e) {
    ensureCapacity(size + 1);  // Increments modCount!!
    elementData[size++= e;
    
return true;
    }
首先检查数组是否已满,如果满了就开始扩容,扩容后的长度为原长度的1.5倍。
/**
     * Increases the capacity of this <tt>ArrayList</tt> instance, if
     * necessary, to ensure that it can hold at least the number of elements
     * specified by the minimum capacity argument.
     *
     * 
@param   minCapacity   the desired minimum capacity
     
*/
    
public void ensureCapacity(int minCapacity) {
    modCount
++;//modCount表示数组的操作计数,用于iterator的时候与
expectedMod
Count比较,防止迭代操作对add,remove等操作影响迭代操作
  
int oldCapacity = elementData.length;
    
if (minCapacity > oldCapacity) {         //新插入元素后的长度大于老的长度,数组开始扩容
        Object oldData[] 
= elementData;
        
int newCapacity = (oldCapacity * 3)/2 + 1;//新空间为原长度的1.5倍,等于是扩容了50%
            
if (newCapacity < minCapacity)
        newCapacity 
= minCapacity;
            
// minCapacity is usually close to size, so this is a win:
            elementData = Arrays.copyOf(elementData, newCapacity);//把之前的元素拷贝到新的数组    }
    }

  • 删除元素:

/**
     * Removes the element at the specified position in this list.
     * Shifts any subsequent elements to the left (subtracts one from their
     * indices).
     *
     * 
@param index the index of the element to be removed
     * 
@return the element that was removed from the list
     * 
@throws IndexOutOfBoundsException {@inheritDoc}
     
*/
    
public E remove(int index) {
    RangeCheck(index); //检查索引是否溢出

    modCount
++;        //操作计数
    E oldValue 
= (E) elementData[index];

    
int numMoved = size - index - 1;
    
if (numMoved > 0)
        System.arraycopy(elementData, index
+1, elementData, index,//复制原数组制定index+1到length-1的元素到elementData的index的索引位
                 numMoved);
    elementData[
--size] = null// Let gc do its work//最后一位设置为null

    
return oldValue;
    }

 /**
     * Checks if the given index is in range.  If not, throws an appropriate
     * runtime exception.  This method does *not* check if the index is
     * negative: It is always used immediately prior to an array access,
     * which throws an ArrayIndexOutOfBoundsException if index is negative.
     
*/
    
private void RangeCheck(int index) {
    
if (index >= size)
        
throw new IndexOutOfBoundsException(
        
"Index: "+index+", Size: "+size);
    }

  • 获取元素:
 /**
     * Returns the element at the specified position in this list.
     *
     * 
@param  index index of the element to return
     * 
@return the element at the specified position in this list
     * 
@throws IndexOutOfBoundsException {@inheritDoc}
     
*/
    
public E get(int index) {
    RangeCheck(index);

    
return (E) elementData[index];   //直接获取数组的索引位
    }
posted @ 2012-02-20 14:28 陈睿 阅读(1024) | 评论 (0)编辑 收藏
posted @ 2012-02-20 14:09 陈睿 阅读(259) | 评论 (0)编辑 收藏
posted @ 2012-02-14 13:15 陈睿 阅读(134) | 评论 (0)编辑 收藏
仅列出标题
共2页: 上一页 1 2 

导航

<2020年8月>
2627282930311
2345678
9101112131415
16171819202122
23242526272829
303112345

统计

常用链接

留言簿

随笔分类

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜