一、ArrayList 和 LinkedList
1.1 联系
ArrayList 和 LinkedList 是 Java 集合框架中用来存储对象引用列表的两个类，都实现了 List 接口。
列表（list）是元素的有序集合，也称为序列。它提供了基于元素位置的操作，有助于快速访问、添加和删除列表中特定索引位置的元素。
List 接口实现了 Collection 和 Iterable 作为父接口。它允许存储重复值和空值，支持通过索引访问元素。
1.2 区别
增加元素
ArrayList
public boolean add(E e){
ensureCapacity(size+1);//确保内部数组有足够的空间
elementData[size++]=e;//将元素加入到数组的末尾，完成添加
return true;
}
public vod ensureCapacity(int minCapacity){
modCount++;
int oldCapacity=elementData.length;
if(minCapacity>oldCapacity){ //如果数组容量不足，进行扩容
Object[] oldData=elementData;
int newCapacity=(oldCapacity*3)/2+1; //扩容到原始容量的1.5倍，hashMap是2倍
if(newCapacitty<minCapacity) //如果新容量小于最小需要的容量，则使用最小
//需要的容量大小
newCapacity=minCapacity ; //进行扩容的数组复制
elementData=Arrays.copyof(elementData,newCapacity);
}
}
- 只要ArrayList的当前容量足够大，add()操作的效率非常高的。只有当ArrayList对容量的需求超出当前数组大小时，才需要进行扩容。
- 扩容的过程中，会进行大量的数组复制操作。而数组复制时，最终将调用System.arraycopy()方法，因此add()操作的效率还是相当高的。
- ArrayList在初始化时可以指定容量，较大的容量可以减少重组的次数。
LinkedList
public boolean add(E e){
addBefore(e,header);//将元素增加到header的前面
return true;
}
private Entry<E> addBefore(E e,Entry<E> entry){
Entry<E> newEntry = new Entry<E>(e,entry,entry.previous);
newEntry.provious.next=newEntry;
newEntry.next.previous=newEntry;
size++;
modCount++;
return newEntry;
}
- LinkeList由于使用了链表的结构，因此不需要维护容量的大小。从这点上说，它比ArrayList有一定的性能优势
- 然而，每次的元素增加都需要新建一个Entry对象，并进行更多的赋值操作。在频繁的系统调用中，对性能会产生一定的影响。
添加元素到指定位置
ArrayList
public void add(int index,E element){
if(index>size||index<0)
throw new IndexOutOfBoundsException(
"Index:"+index+",size: "+size);
ensureCapacity(size+1);
System.arraycopy(elementData,index,elementData,index+1,size-index);
elementData[index] = element;
size++;
}
每次插入操作，都会进行一次数组复制。而这个操作在增加元素到List尾端的时候是不存在的，大量的数组重组操作会导致系统性能低下。
LinkedList
public void add(int index,E element){
addBefore(element,(index==size?header:entry(index)));
}
对LinkedList来说，在List的尾端插入数据与在任意位置插入数据是一样的，不会因为插入的位置靠前而导致插入的方法性能降低。
删除元素
ArrayList
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,numMoved);
elementData[--size]=null;
return oldValue;
}
对ArrayList来说，remove()方法和add()方法是雷同的。在任意位置移除元素后，都要进行数组的重组。
LinkedList
public E remove(int index){
return remove(entry(index));
}
private Entry<E> entry(int index){
if(index<0 || index>=size)
throw new IndexOutBoundsException("Index:"+index+",size:"+size);
Entry<E> e= header;
if(index<(size>>1)){//要删除的元素位于前半段
for(int i=0;i<=index;i++)
e=e.next;
}else{
for(int i=size;i>index;i--)
e=e.previous;
}
return e;
}
- 首先要通过循环找到要删除的元素。如果要删除的位置处于List的前半段，则从前往后找；若其位置处于后半段，则从后往前找，是比较高效的；
- 但要移除List中间的元素却几乎要遍历完半个List，在List拥有大量元素的情况下，效率很低。
遍历列表
//构造一个拥有100万数据的ArrayList和等价的LinkedList
String tmp;
long start=System.currentTimeMills(); //ForEach
for(String s:list){
tmp=s;
}
System.out.println("foreach spend:"+(System.currentTimeMills()-start));
start = System.currentTimeMills();
for(Iterator<String> it=list.iterator();it.hasNext();){
tmp=it.next();
}
System.out.println("Iterator spend;"+(System.currentTimeMills()-start));
start=System.currentTimeMills();
int size=;list.size();
for(int i=0;i<size;i++){
tmp=list.get(i);
}
System.out.println("for spend;"+(System.currentTimeMills()-start));
- 最简便的ForEach循环并没有很好的性能表现，综合性能不如普通的迭代器
- 用for循环通过随机访问遍历列表时，ArrayList表项很好，但是LinkedList的表现却无法让人接受，甚至没有办法等待程序的结束。这是因为对LinkedList进行随机访问时，总会进行一次列表的遍历操作。性能非常差，应避免使用。
1.3 总结
- 对ArrayList和LinkedList而言，在列表末尾增加一个元素所花的开销都是固定的。对ArrayList而言，主要是在内部数组中增加一项，指向所添加的元素，偶尔可能会导致对数组重新进行分配；而对LinkedList而言，这个开销是统一的，分配一个内部Entry对象。
- 在ArrayList的中间插入或删除一个元素意味着这个列表中剩余的元素都会被移动；而在LinkedList的中间插入或删除一个元素的开销是固定的。
- LinkedList不支持高效的随机元素访问。
- ArrayList的空间浪费主要体现在在list列表的结尾预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间
二、HashMap 和 TreeMap
2.1 区别
实现
- TreeMap<K,V>的Key值是要求实现java.lang.Comparable，所以迭代的时候TreeMap默认是按照Key值升序排序的，构造时可以传入Comparator自定义排序。
- HashMap<K,V>的Key值实现散列hashCode()，分布是散列的、均匀的，不支持排序；
数据结构
- TreeMap的实现是基于红黑树结构。适用于按自然顺序或自定义顺序遍历键（key）。
- 数据结构主要是桶(数组)，链表或红黑树。适用于在Map中插入、删除和定位元素。
调优
- TreeMap没有调优选项，因为该树总处于平衡状态。
- 为了优化HashMap空间的使用，可以调优初始容量和负载因子。
使用场景
- 如果需要得到一个有序的结果时就应该使用TreeMap（因为HashMap中元素的排列顺序是不固定的）。
- 由于HashMap有更好的性能，所以大多不需要排序的时候我们会使用HashMap。
2.2 相同点
HashMap 和 TreeMap 都是非线程安全
三、HashMap的hash冲突
3.1 HashMap概述
- HashMap基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。
- 除了不同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。
- 如果想要线程安全的HashMap，可以通过Collections类的静态方法synchronizedMap获得线程安全的HashMap。
- HashMap底层是通过链表来解决hash冲突的
3.2 Hash算法
HashMap 采用一种所谓的“Hash 算法”来决定每个元素的存储位置。
当程序执行 map.put(key,value)方法 时，系统调用key对象的hashCode() 方法得到其 hashCode 值并决定该元素的存储位置。
图中，紫色部分即代表哈希表，也称为哈希数组，数组的每个元素都是一个单链表的头节点，链表是用来解决冲突的，如果不同的key映射到了数组的同一位置处，就将其放入单链表中。
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,V> e = table[i]; e != null; e = e.next) {
Object k;
//判断当前确定的索引位置是否存在相同hashcode和相同key的元素，如果存在相同的hashcode和相同的key的元素，那么新值覆盖原来的旧值，并返回旧值。
//如果存在相同的hashcode，那么他们确定的索引位置就相同，这时判断他们的key是否相同，如果不相同，这时就是产生了hash冲突。
//Hash冲突后，那么HashMap的单个bucket里存储的不是一个 Entry，而是一个 Entry 头插法单链表。
//系统只能必须按顺序遍历每个 Entry，直到找到想搜索的 Entry 为止——如果恰好要搜索的 Entry 位于该 Entry 链的最末端（该 Entry 是最早放入该 bucket 中），
//那系统必须循环到最后才能找到该元素。
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
//系统总是将新添加的 Entry 对象放入 table 数组的 bucketIndex 索引处，最终形成一个头插法单链表。
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
if (size++ >= threshold)
resize(2 * table.length);
bsp;
- 可以把 Map 集合中的 value 当成 key 的附属，当系统决定了 key 的存储位置之后，value 随之保存在那里
- HashMap里面没有出现hash冲突时，没有形成单链表时，hashmap查找元素很快,get()方法能够直接定位到元素，出现单链表后，系统只能必须按顺序遍历搜索链表中每个 Entry。
- 负载因子默认0.75，是时间和空间成本的一种折衷。增大负载因子可以减少 Hash 表（就是那个 Entry 数组）所占用的内存空间，但会增加查询数据的时间开销，而查询是最频繁的的操作（HashMap 的 get() 与 put() 方法都要用到查询）；减小负载因子会提高数据查询的性能，但会增加 Hash 表所占用的内存空间。
3.3 Map.Entry类
/** Entry是单向链表。
* 它是 “HashMap链式存储法”对应的链表。
*它实现了Map.Entry 接口，即实现getKey(), getValue(), setValue(V value), equals(Object o), hashCode()这些函数
**/
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
// 指向下一个节点
Entry<K,V> next;
final int hash;
// 构造函数。
// 输入参数包括"哈希值(h)", "键(k)", "值(v)", "下一节点(n)"
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
public final K getKey() {
return key;
}
public final V getValue() {
return value;
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
// 判断两个Entry是否相等
// 若两个Entry的“key”和“value”都相等，则返回true。
// 否则，返回false
public final boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry)o;
Object k1 = getKey();
Object k2 = e.getKey();
if (k1 == k2 || (k1 != null && k1.equals(k2))) {
Object v1 = getValue();
Object v2 = e.getValue();
if (v1 == v2 || (v1 != null && v1.equals(v2)))
return true;
}
return false;
}
// 实现hashCode()
public final int hashCode() {
return (key==null ? 0 : key.hashCode()) ^
(value==null ? 0 : value.hashCode());
}
public final String toString() {
return getKey() + "=" + getValue();
}
// 当向HashMap中添加元素时，绘调用recordAccess()。
// 这里不做任何处理
void recordAccess(HashMap<K,V> m) {
}
// 当从HashMap中删除元素时，绘调用recordRemoval()。
// 这里不做任何处理
void recordRemoval(HashMap<K,V> m) {
}
}
HashMap其实就是一个Entry数组，Entry对象中包含了键和值，其中next也是一个Entry对象，它就是用来处理hash冲突的，形成一个链表。
四、序列化
4.1 定义
序列化
- 对象序列化的最主要的用处就是在传递和保存对象的时候，保证对象的完整性和可传递性。
- 序列化把对象转换成有序字节流，以便在网络上传输或者保存在本地文件中。
- 核心作用是对象状态的保存与重建。
反序列化
- 客户端从文件中或网络上获得序列化后的对象字节流，根据字节流中所保存的对象状态及描述信息，通过反序列化重建对象。
4.2 用途
分布式对象。
如：RMI(即远程调用Remote Method Invocation)要利用对象序列化运行远程主机上的服务，就像在本地机上运行对象时一样。
深拷贝
可以将整个对象层次写入字节流中，可以保存在文件中或在网络连接上传递。
利用对象序列化可以进行对象的"深复制"，即复制对象本身及引用的对象本身。
持久化
将某个类序列化后存为文件，下次读取时只需将文件中的数据反序列化就可以将原先的类还原到内存中。也可以将类序列化为流数据进行传输。
总的来说就是将一个已经实例化的类转成文件存储，下次需要实例化的时候只要反序列化即可将类实例化到内存中并保留序列化时类中的所有变量和状态。
4.3 实现
实现 Serializabel接口
import java.io.Serializable;
public class Person implements Serializable { //本类可以序列化
private String name;
private int age;
public Person(String name, int age) {
this.name = name;
this.age = age;
}
public String toString() {
return "姓名：" + this.name + "，年龄" + this.age;
}
}
序列化
package org.lxh.SerDemo;
import java.io.File;
import java.io.FileOutputStream;
import java.io.ObjectOutputStream;
public class ObjectOutputStreamDemo { //序列化
public static void main(String[] args) throws Exception {
//序列化后生成指定文件路径
File file = new File("D:" + File.separator + "person.ser");
ObjectOutputStream oos = null;
//装饰流（流）
oos = new ObjectOutputStream(new FileOutputStream(file));
//实例化类
Person per = new Person("张三", 30);
oos.writeObject(per); //把类对象序列化
oos.close();
}
}
五、Comparable和Comparator
Comparable 和 Comparator，二者都是用来实现对象的比较、排序。
5.1 Comparable
- Comparable可以认为是一个内比较器，实现了Comparable接口的类有一个特点，就是这些类是可以和自己比较的，至于具体和另一个实现了Comparable接口的类如何比较，则依赖compareTo方法的实现。
- 如果add进入一个Collection的对象想要Collections的sort方法帮你自动进行排序的话，那么这个对象必须实现Comparable接口。
代码里面Comparable的泛型未必就一定要是Domain，将泛型指定为String或者指定为其他任何任何类型都可以
public class Domain implements Comparable<Domain>
{
private String str;
public Domain(String str)
{
this.str = str;
}
public int compareTo(Domain domain)
{
if (this.str.compareTo(domain.str) > 0)
return 1;
else if (this.str.compareTo(domain.str) == 0)
return 0;
else
return -1;
}
public String getStr()
{
return str;
}
}
5.2 Comparator
- Comparator接口里面有一个compare方法，方法有两个参数T o1和T o2，是泛型的表示方式，分别表示待比较的两个对象。
- 因为泛型指定死了，所以实现Comparator接口的实现类只能是两个相同的对象（不能一个Domain、一个String）进行比较了，实现Comparator接口的实现类一般都会以"待比较的实体类+Comparator"来命名
public class DomainComparator implements Comparator<Domain>
{
public int compare(Domain domain1, Domain domain2)
{
if (domain1.getStr().compareTo(domain2.getStr()) > 0)
return 1;
else if (domain1.getStr().compareTo(domain2.getStr()) == 0)
return 0;
else
return -1;
}
}
5.3 总结
- 如果实现类没有实现Comparable接口，又想对两个类进行比较（或者实现类实现了Comparable接口，但是对compareTo方法内的比较算法不满意），那么可以实现Comparator接口，自定义一个比较器，写比较算法。
- 实现Comparable接口的方式比实现Comparator接口的耦合性要高一些，适用于已经实现Comparble接口的基本数据类型。
六、HashMap线程不安全
HashMap是线程不安全的，在多线程环境中不建议使用。
在jdk1.7中，在多线程环境下，扩容时会造成环形链(造成死循环)或数据丢失。
在jdk1.8中，在多线程环境下，会发生数据覆盖的情况。
Q.E.D.
Comments | 0 条评论