参考https://blog.csdn.net/u011240877/category_6447444.html

ArrayList 扩容机制：

jdk1.8的扩容算法：newCapacity = oldCapacity + ( oldCapacity >> 1 ) ; // oldCapacity >> 2 移位运算，此处相当于oldCapacity除以2，但是 >> 这种写法更加高效

jdk1.6的扩容算法：newCapacity = ( oldCapacity * 3 ) / 2 +1 ;

参数介绍：newCapacity 是扩容后的容量大小，oldCapacity 是扩容前的大小
————————————————
版权声明：本文为CSDN博主「森森之火」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/yb546822612/article/details/106225049

ArrayList各方法的时间复杂度

add(E e)方法
添加元素到末尾，平均时间复杂度为O(1)。

add(int index, E element)方法
添加元素到指定位置，平均时间复杂度为O(n)。

get(int index)方法
获取指定索引位置的元素，时间复杂度为O(1)。

remove(int index)方法
删除指定索引位置的元素，时间复杂度为O(n)。

remove(Object o)方法
删除指定元素值的元素，时间复杂度为O(n)。
————————————————
版权声明：本文为CSDN博主「Thxxxxxx」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_29066329/article/details/91626776

LinkedList的复杂度？

get() 获取第几个元素，依次遍历，复杂度O(n)
add(E) 添加到末尾，复杂度O(1)
add(index, E) 添加第几个元素后，需要先查找到第几个元素，直接指针指向操作，复杂度O(n) （这个比较容易想错）
remove（）删除元素，直接指针指向操作，复杂度O(1)
————————————————
版权声明：本文为CSDN博主「pmdream」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/pmdream/article/details/107016062

Vector扩容机制

jdk1.8的扩容算法：newCapacity = oldCapacity + ( ( capacityIncrement > 0 ) ? capacityIncrement : oldCapacity );

jdk1.6的扩容算法：newCapacity = ( capacityIncrement > 0 ) ? ( oldCapacity + capacityIncrement ) : ( oldCapacity * 2 );

参数介绍：capacityIncrement 是容量修正（即容量新增大小），没有设置，默认为0 ，newCapacity 是扩容后的容量大小，oldCapacity 是扩容前的大小

一观察，就会发现1.6与1.8的写法变化不大，但是仔细一分析，就会发现jdk1.6中有使用乘法运算，即 oldCapacity * 2。 在jdk1.8中换成了加法运算，这是因为乘法的效率是低于加法的，这应该算法的优化。
————————————————
版权声明：本文为CSDN博主「森森之火」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/yb546822612/article/details/106225049

HashMap 实现原理和特点

HashMap 的特点
结合平时使用，可以了解到 HashMap 大概具有以下特点：

1. 底层实现是 链表数组，JDK 8 后又加了 红黑树
   实现了 Map 全部的方法
2. key 用 Set 存放，所以想做到 key 不允许重复，key 对应的类需要重写 hashCode 和 equals 方法
3. 允许空键和空值（但空键只有一个，且放在第一位，下面会介绍）
4. 元素是无序的，而且顺序会不定时改变
5. 插入、获取的时间复杂度基本是 O(1)（前提是有适当的哈希函数，让元素分布在均匀的位置）
6. 遍历整个 Map 需要的时间与 桶(数组) 的长度成正比（因此初始化时 HashMap 的容量不宜太大）
7. 两个关键因子：初始容量、加载因子
   除了不允许 null 并且同步，Hashtable 几乎和他一样。
   ————————————————
   版权声明：本文为CSDN博主「拭心」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
   原文链接：https://blog.csdn.net/u011240877/article/details/53351188
   
   image.png

注意

1、哈希冲突百分百的类

    /**
    测试哈希冲突的类，所有的对象都返回同样的hash值
   **/
    public static class Student{
        private String name;
        Student(String name){
            this.name = name;
        }
 
        @Override
        public int hashCode(){
            return 1;
        }
 
        @Override
        public boolean equals(Object obj){
            if(this == obj){
                return true;
            }
            if(obj == null){
                return false;
            }
            return this.name.equals(((Student)obj).name);
        }
    }

2、我们在实际使用hashmap时需要确保实现hashcode方法以及equals方法，否则不能作为hashmap的键值

3、在设置hashmap的键值hashcode方法时尽量保证较好的离散型

4、hashmap的键值需保证equals方法返回true时，hashcode必须相同，所以在实际中经常使用的键值类string，重写了equals以及hashcode方法
————————————————
版权声明：本文为CSDN博主「PolarisHuster」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/john1337/article/details/104727895

HashMap 优化