深入arraylist,linkedlist,hashmap,hashset源码(2012/3/18)

1.冒泡排序
2.arraylist存放的是对象的引用,不是对象本身,在java里面除了8中基本类型(int ,double ,long ,short,char,byte,boolean,float)
3.你做相似的工作又多种选择的时候，可以考虑用抽象工厂
这个抽象工厂运用他的场景：
1。你有两台单色打印机，一台黑白墨的，一台彩墨的。
2。你有两种文件要打，一种讲演搞，一种图片
3.ArrayList底层采用数组实现,当使用不带参数的构造方法生成ArrayList对象时,
  调用arraylist默认构造函数时,实际上会在底层生成一个长度为10的Object类型的数组.
4.如果增加的元素个数超过10个,那么ArrayList底层会新生成一个数组,长度为原数组的1.5倍+1,然后将原数组的内容复制到新数组中,并且后续增加的内容都
hi放到新数组中,当新数组无法容纳增加的元素时,重复该过程.
5.arraylist底层采用数组实现,linkedList底层采用双向链表实现,当执行插入或者删除时,linkedlist好
执行收索时arraylist好(下标)
6.集合添加时用hascode(字符相等),equals判断。(重写hascode跟equals方法)
   HashSet 首先判断hascode是否相同不同则加进去,否则判断equals方法是否返回true,若为false则不加进去。
7.HashSet(按散列放到什么位置不是按顺序)底层是用HashMap实现的,当使用add方法将对象添加到set当中时，实际上是将该对象作为底层所维护的Map
对象的key,而value则都是同一个对象Object对象(该对象用不上)。
8.hashmap(数组+链表)底层维护一个数组(hash碰撞),我一对们向HashMap中所放置的对象实际上是储存在该数组当中.
9.当向HashMap中put一对键值时,他会根据key的hashcode值计算出一个位置,该位置就是此对象准备往数组存放的位置。
如果该位置没有对象存在,直接把该对象放进数组当中,如果该位置已经有对象存在了,
则顺着次存在的对象的链表开始寻找(Entry类有一个Entry类型的next成员变量,指向了该对象的下一个对象)，
如果此链上有对象的话,再去使用equlas方法进行比较,
如果对此链表上的某个对象的equals方法比较为false,则将该对象放到数组当中,然后将数组当中的该位置以前存在的那个对象链表到此对象的后面。
hashmap get
 
    public V get(Object key) {
        if (key == null)
            return getForNullKey();
        int hash = hash(key.hashCode());
        for (Entry<k> 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;
    }
hashmap  put

    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<k> 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;
    }

10.java中底层只有数组，链表,数组管理多个对象。</k></k>


Hashset跟Treeset的区别
  1.HashSet 是哈希表实现的，无序的结合,表现为检索(contains)的时间复杂度是 o(0)
    TreeSet 是红黑树实现的，排序的集合
    先看看源码：
public class TreeSet
    extends AbstractSet
    implements SortedSet, Cloneable, java.io.Serializable
public class HashSet
    extends AbstractSet
    implements Set, Cloneable, java.io.Serializable
其中SortedSet中组合了一个：Comparator  super E> comparator();
  2.TreeSet与HashSet最大区别在于排序
  3.Treeset中的数据是自动排好序的，不允许放入null值
  2.HashSet中的数据是无序的，可以放入null，但只能放入一个null，两者中的值都不能重复，就如数据库中唯一约束
  3.HashSet要求放入的对象必须实现HashCode()方法，放入的对象，是以hashcode码作为标识的，而具有相同内容的String对象，
   hashcode是一样，所以放入的内容不能重复。但是同一个类的对象可以放入不同的实例

今天有人问这个，发现自己只是大概理解而且只会用了。该忘的竟然忘得差不多了，翻翻书复习下。

对于处理一列数据项，Java提供了两个类ArrayList和LinkedList。
ArrayList的内部实现是基于内部数组Object[]，所以从概念上讲，它更像数组、
但LinkedList的内部实现是基于一组连接的记录，所以，它更像一个链表结构，所以，它们在性能上有很大的差别。

在ArrayList的前面或中间插入数据时，必须将其后的所有数据相应的后移，这样必然要花费较多时间，所以，当你的操作是在一列数据的后面添加数据而不是在前面或中间，并且需要随机地访问其中的元素时，使用ArrayList会提供比较好的性能；

而访问链表中的某个元素时，就必须从链表的一端开始沿着连接方向一个一个元素地去查找，直到找到所需的元素为止，所以，当你的操作是在一列数据的前面或中间添加或删除数据，并且按照顺序访问其中的元素时，就应该使用LinkedList了。

如果在编程中，两种情形交替出现，这时，可以考虑使用List这样的通用接口，而不用关心具体的实现，在具体的情形下，它的性能由具体的实现来保证。

ArrayList的查询效率比较高，增删动作的效率比较差，适用于查询比较频繁，增删动作较少的元素管理的集合。LinkedList的查询效率低，但是增删效率很高。适用于增删动作的比较频繁，查询次数较少的元素管理集合。

ArrayList，LinkedList都是线程不安全的。

StringBuilder、StringBuffer和String三者的联系和区别

1. String 类
   　　String的值是不可变的，这就导致每次对String的操作都会生成新的String对象，不仅效率低下，而且大量浪费有限的内存空间。
   String a = "a"; //假设a指向地址0x0001
   a = "b";//重新赋值后a指向地址0x0002，但0x0001地址中保存的"a"依旧存在，但已经不再是a所指向的,a 已经指向了其它地址。
   因此String的操作都是改变赋值地址而不是改变值操作。

2. StringBuffer是可变类，和线程安全的字符串操作类，任何对它指向的字符串的操作都不会产生新的对象。 每个StringBuffer对象都有一定的缓冲区容量，当字符串大小没有超过容量时，不会分配新的容量，当字符串大小超过容量时，会自动增加容量。

   StringBuffer buf=new StringBuffer(); //分配长16字节的字符缓冲区
   StringBuffer buf=new StringBuffer(512); //分配长512字节的字符缓冲区
   StringBuffer buf=new StringBuffer("this is a test")//在缓冲区中存放了字符串，并在后面预留了16字节的空缓冲区。

3.StringBuffer
　　StringBuffer和StringBuilder类功能基本相似，主要区别在于StringBuffer类的方法是多线程、安全的，而StringBuilder不是线程安全的，相比而言，StringBuilder类会略微快一点。对于经常要改变值的字符串应该使用StringBuffer和StringBuilder类。

4.线程安全
StringBuffer 线程安全
StringBuilder 线程不安全

5.速度
一般情况下,速度从快到慢:StringBuilder>StringBuffer>String,这种比较是相对的，不是绝对的。

6.总结
（1）.如果要操作少量的数据用 = String
（2）.单线程操作字符串缓冲区 下操作大量数据 = StringBuilder
（3）.多线程操作字符串缓冲区 下操作大量数据 = StringBuffer