JAVA 常用集合内部机制原理

mf3572 5年前
   <p>对于常用的集合大家都不陌生,但是深入到内部原理可能都是一知半解,通过阅读源码理解如下。</p>    <h2><br> <strong>ArrayList</strong></h2>    <p>ArrayList内部就是一个默认大小为10的动态对象数组容器,每当add一个新数据的时候,如果大于原来的容器大小,则会通过Arrays.copyOf把容器大小增加到原来的1.5倍,以此类推。当可以预知数据大小,可以通过initialCapacity来默认设置动态数据的大小,减少扩容带来的资源消耗。</p>    <p><br> 时间复杂度:</p>    <p>get() - 直接读取下标 - O(1)</p>    <p>add(E) - 直接在后面添加 - O(1)</p>    <p>add(idnex, E) - 插入数据后需要移动后面的数据 - O(n)</p>    <p>remove(index) - 删除后需要移动 - O(n)</p>    <h2><br> <strong>LinkedList</strong></h2>    <p>LinkedList内部是一个双向链表,add新数据的时候,其实就是调用linklast在链表尾部插入数据。删除的时候直接找到对应数据,替换掉链表的前后节点即可。</p>    <p>时间复杂度:</p>    <p>get() - 需要遍历 - O(n)</p>    <p>add(E) - 调用linklast直接添加在最后 - O(1)</p>    <p>add(index, E) - 需要先查找到原来index位置的数据,再重新指定链表前后的数据 - O(n)</p>    <p>remove() - 直接调用removeLast删除最后数据 - O(1)</p>    <p>remove(index) - 需要先查找到原来index位置的数据 - O(n)</p>    <h2><br> <strong>HashMap</strong></h2>    <p>HashMap内部其实是一个数组,每个数组下是一个单向链表。HashMap中的数组是一个取名为Entry的类,类包含(key, value, next)这几个属性。存放规则为,数组下标按hash(key)%len获得,取得数组后则查找对应数组的值。HashMap还有个负载因子(默认0.75),当里面数组填满了75%的时候,会进行扩展到原来大小的2倍。</p>    <p>那么问题来了,如果在put的时候,取到hash(key)%len的值相等时不就冲突了?HashMap的处理方法是:原来有一个Entry[0] = A,此时来一个index也是0的B,则会把Entry[0] = B,B.next = A,又来一个C的时候,则会把Entry[0] = C,C.next = B,以此类推。这样Entry就会形成一个链表,取的时候则是遍历链表取值。</p>    <p>这里需要提到的是,使用hashMap的时候,引入的key对象必须重写hashCode()和equal()两个函数,原因可以参考源码判断条件(if (e.hash == hash && ((k = e.key) == key || key.equals(k)))),如果hashCode()没重写,则压根找不到对应数组,如果equal()没重写,则无法判断key值的内容是否相等。</p>    <pre>  <code class="language-java">public V put(K key, V value) {            if (key == null)                return putForNullKey(value); //null总是放在数组的第一个链表中            int hash = hash(key.hashCode());            int i = indexFor(hash, table.length);            //遍历链表            for (Entry<K,V> e = table[i]; e != null; e = e.next) {                Object k;                //如果key在链表中已存在,则替换为新value                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;    }</code></pre>    <p><br> 补充:</p>    <p>在java8之后hashmap进行了优化:由于单向链表的查询时间复杂度为O(n),在极端情况下可能存在性能问题,于是java8针对链表长度大于8的情况会使用时间复杂度为O(log n)的红黑树进行存储来提升存储查询的效率。</p>    <p>LinkedHashMap</p>    <p>LinkedHashMap内部双向链表和HashMap的结合,支持多种迭代顺序,默认按插入顺序,也可以按访问顺序。 </p>    <p>访问顺序(accessOrder=true):调用过get访问的元素会放到链尾,迭代会从链首开始</p>    <p>插入顺序(accessOrder=false):按插入顺序迭代出来</p>    <h2><strong>TreeMap</strong></h2>    <p>TreeMap内部是基于红黑树实现的,并且默认会通过compareTo按照key类型进行自然排序。TreeSet的低层是TreeMap。</p>    <p> </p>    <p> </p>    <p>来自:http://www.jointforce.com/jfperiodical/article/4192</p>    <p> </p>