再谈Java数据结构—分析底层实现与应用注意事项
原创
在回顾js数据结构，写《再谈js对象数据结构底层实现原理-object array map set》系列的时候，在来整理下java的数据结构。
java把内存分两种：一种是栈内存，另一种是堆内存
- 基本类型在栈区分配空间，java的基本数据类型共有8种，即int,short,long,byte,float,double,boolean,char(注意，并没有String的基本类型 )。由于大小可知，生存期可知(这些字面值定义在某个程序块里面，程序块退出后，字段值就消失了)，出于追求速度的原因，就存在于栈中。
- 所有的对象都在堆(Heap)中分配空间，关键字new为每个对象申请内存空间(基本类型除外)，对象的释放是由垃圾回收机制决定和执行的，这样做确实简化了程序员的工作。但同时，它也加重了JVM的工作。因为，GC为了能够正确释放对象，GC必须监控每一个对象的运行状态，包括对象的申请、引用、被引用、赋值等，GC都需要进行监控。 不要在经常调用的方法中或在循环中创建对象。可以适当的使用hashtable，vector创建一组对象容器，然后从容器中去取那些对象，而不用每次new之后又丢弃。尽量避免在类的构造函数里创建、初始化大量的对象，防止在调用其自身类的构造器时造成不必要的内存资源浪费，尤其是大对象
包装类
基本类型都有对应的包装类：如int对应Integer类，double对应Double类等，基本类型的定义都是直接在栈中，如果用包装类来创建对象，就和普通对象一样了。例如：int i=0；i直接存储在栈中。Integer i（i此时是对象）= new Integer(5)；这样，i对象数据存储在堆中，i的引用存储在栈中，通过栈中的引用来操作对象。大量使用字符串处理，避免使用String，应大量使用StringBuffer，因为String被设计成不可变(immutable)类，所以它的所有对象都是不可变对象
数组
当定义一个数组，int x[]；或int[] x；时，在栈内存中创建一个数组引用，通过该引用（即数组名）来引用数组。x=new int3；将在堆内存中分配3个保存 int型数据的空间，堆内存的首地址放到栈内存中，每个数组元素被初始化为0。
静态变量
用static的修饰的变量和方法，实际上是指定了这些变量和方法在内存中的”固定位置”－static storage，可以理解为所有实例对象共有的内存空间。static变量有点类似于C中的全局变量的概念；静态表示的是内存的共享，就是它的每一个实例都指向同一个内存地址。把static拿来，就是告诉JVM它是静态的，它的引用（含间接引用）都是指向同一个位置，在那个地方，你把它改了，它就不会变成原样，你把它清理了，它就不会回来了。
那静态变量与方法是在什么时候初始化的呢？对于两种不同的类属性，static属性与instance属性，初始化的时机是不同的。instance属性在创建实例的时候初始化，static属性在类加载，也就是第一次用到这个类的时候初始化，对于后来的实例的创建，不再次进行初始化。
尽量少用静态变量，因为静态变量是全局的，GC不会回收的。
数组Array和集合的区别
- 1 长度限制之别
- 数组长度是固定不变的，
- 集合的大小是可动态变化的
- 2 存储类型之别
- 一个数组存储的元素可以是基本类型，也可以是引用类型，且只能存储同一种类型的元素
- 一个集合存储的元素只能是引用类型，但集合可以存储不同类型的元素(但集合一般存储同一种类型，可以用泛型加以控制)
- 3 访问元素方式
- 数组是根据索引来获取元素的
- 集合通常会提供一个迭代器来方便访问元素
若程序时不知道究竟需要多少对象，需要在空间不足时自动扩增容量，则需要使用容器类库，array不适用。
java集合是什么？
Java集合类存放于 java.util 包中，是一个用来存放对象的容器。
- 长度限制之别：集合只能存放对象。比如你存一个 int 型数据 1放入集合中，其实它是自动转换成 Integer 类后存入的，Java中每一种基本类型都有对应的引用类型。
- 集合存放的是多个对象的引用，对象本身还是放在堆内存中。
- 集合可以存放不同类型，不限数量的数据类型。
史上最全Java集合关系图 ?，java集合关系UML类图vsdx原图。
Collection
? ? |-----List 有序，可重复(存储顺序和取出顺序一致)
? ? |--|----LinkedList?底层使用双向链表实现，查询慢，增删快。效率高
? ? |--|----ArrayList 底层使用数组实现，查询快，增删慢。效率高。
? ? |? |? ? ? ? 每次容量不足时，自增长度的一半，如下源码可知
? ? |? |? ? ? ? ? int newCapacity = oldCapacity + (oldCapacity >> 1);
? ? |--|----Vector 底层使用数组实现，线程安全，查询快，增删慢。效率低。
? ? |? |? ? ? ? 每次容量不足时，默认自增长度的一倍（如果不指定增量的话），如下源码可知
? ? |? |? ? ? ? ? int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
? ? |? |? ? ? ? ? ? ? ? ? ? ? ? ? ? capacityIncrement : oldCapacity);
? ? |-----Set 元素唯一(最多包含一个 null 元素)，只能通过游标来取值，线程不安全
? ? ? ? ? ?HashSet比TreeSet高效(尤其是查询、添加),LinkedHashSet比hash插入、删除慢，但是遍历快。
? ? |--|--HashSet 底层是由HashMap实现的，线程非安全，通过对象的hashCode方法与equals方法来保证插入元素的唯一性，无序(存储顺序和取出顺序不一致)?
? ? |--|--|--LinkedHashSet 底层数据结构由哈希表和链表组成。哈希表保证元素的唯一性，链表保证元素有序。(存储和取出是一致)
? ? |--|--TreeSet 基于 TreeMap 的 NavigableSet 实现。非同步，排序，元素唯一。?保持有序的set使用(使用元素的自然顺序对元素进行排序，或者根据创建 set 时提供的 Comparator 进行排序(红黑数维护次序)
Map 是键值对集合,key 不允许重复，value 可以
? ? |-----HashMap?基于链表和红黑树:hashMap用hash表实现的Map,就是利用对象的hashcode(hashcode()是Object的方法)进行快速散列查找。Null可以做主键，但只能有一个
? ? |-----TreeMap 基于红黑树
? ? |-----LinkedHashMap?HashMap+LinkedList
? ? |-----HashTable?线程安全，不允许有null值的存在
java集合框架概括
只有Vector，HashTable是线程安全的
ArrayList，LinkedList，HashSet，TreeSet，HashMap，TreeMap都不是线程安全的。
如果没有必要,推荐代码只同List,Map接口打交道.
HashMap的输出顺序是随机的，TreeMap中的条目是按键值的升序排列的，LinkedHashMap是按元素最后一次被访问的时间从早到晚排序的
简明图
Collection||Set泛型接口方法摘要
boolean?add(E?e)
????确保此?collection?包含指定的元素（可选操作）。
boolean?addAll(Collection?c)
????将指定?collection?中的所有元素都添加到此?collection?中（可选操作）。
void?clear()
????移除此?collection?中的所有元素（可选操作）。
boolean?contains(Object?o)
????如果此?collection?包含指定的元素，则返回?true。
boolean?containsAll(Collection?c)
????如果此?collection?包含指定?collection?中的所有元素，则返回?true。
boolean?equals(Object?o)
????比较此?collection?与指定对象是否相等。
int?hashCode()
????返回此?collection?的哈希码值。
boolean?isEmpty()
????如果此?collection?不包含元素，则返回?true。
Iterator?iterator()
????返回在此?collection?的元素上进行迭代的迭代器。
boolean?remove(Object?o)
????从此?collection?中移除指定元素的单个实例，如果存在的话（可选操作）。?
boolean?removeAll(Collection?c)
????移除此?collection?中那些也包含在指定?collection?中的所有元素（可选操作）。
boolean?retainAll(Collection?c)
????仅保留此?collection?中那些也包含在指定?collection?的元素（可选操作）。
int?size()
????返回此?collection?中的元素数。
Object[]?toArray()
????返回包含此?collection?中所有元素的数组。?T[]
????toArray(T[]?a)List泛型接口
特有方法(相对于Collection—继承自Collection)
void?add(int?index,?E?element)
????在列表的指定位置插入指定元素（可选操作）。
boolean?addAll(int?index,?Collection?c)
????将指定?collection?中的所有元素都插入到列表中的指定位置（可选操作）。
int?indexOf(Object?o)
????返回此列表中第一次出现的指定元素的索引；如果此列表不包含该元素，则返回?-1。
int?lastIndexOf(Object?o)
????返回此列表中最后出现的指定元素的索引；如果列表不包含此元素，则返回?-1。
ListIterator?listIterator()
????返回此列表元素的列表迭代器（按适当顺序）。
ListIterator?listIterator(int?index)
????返回列表中元素的列表迭代器（按适当顺序），从列表的指定位置开始。
E?get(int?index)
????返回列表中指定位置的元素。
E?remove(int?index)
????移除列表中指定位置的元素（可选操作）。
E?set(int?index,?E?element)
????用指定元素替换列表中指定位置的元素（可选操作）。
List?subList(int?fromIndex,?int?toIndex)
????返回列表中指定的?fromIndex（包括?）和?toIndex（不包括）之间的部分视图。原文链接：/developer/article/1176768 排版效果可能更好，本文若有不妥之处，请留言告知，拜谢！
参考文章：
java 集合详解 https://www.cnblogs.com/ysocean/p/6555373.html
java集合详解与基本使用方法 https://blog.csdn.net/qq_34232889/article/details/79997471
图解Java常用数据结构 https://www.jianshu.com/p/fb4fb24ecc8f
java中的集合和数组 https://www.cnblogs.com/summers/p/4094260.html
集合的线程安全性 https://www.cnblogs.com/wuchaodzxx/p/6007970.html
Set与线程安全 https://blog.csdn.net/l153097889/article/details/77891250
java常用数据结构及特点 https://blog.csdn.net/hujiangtaochn/article/details/84136432
Java集合框架之图解 https://www.cnblogs.com/SamSarah/p/4893217.html
java.util包中集合详解 https://www.jianshu.com/p/4bb01e139cda
使Cache命中率最高的替换算法是什么？替换最近最少使用的块算法
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。