数据结构(比对篇)

ArrayList和LinkedList

作为一个纯粹的数据存储介质，当然从增删改查三个方面比较他们的性能问题！

新增性能

头部插入

List list1 = new ArrayList();
List list2 = new LinkedList();
long start11 = System.currentTimeMillis();
for (int i = 0; i < 10000000; i++) {list1.add(i);
}
long start12 = System.currentTimeMillis();
System.out.println(start12-start11);long start21 = System.currentTimeMillis();
for (int i = 0; i < 10000000; i++) {list2.add(i);
}
long start22 = System.currentTimeMillis();
System.out.println(start22-start21);#输出结果4141697

结论：ArrayList比LinkedList快

原因分析：按序插入时，ArrayList添加元素直接在数组上新增，Linkedlist链表添加需要执行两步：

​ 1、指定最后一个元素的末位置是新元素的head

​ 2、标记新元素为链表最后一个

指定下标插入

List list1 = new ArrayList();
List list2 = new LinkedList();
for (int i = 0; i < 10000000; i++) {list1.add(i);list2.add(i);
}long start11 = System.currentTimeMillis();
for (int i = 0; i < 1000; i++) {list1.add(i + 2, i);
}
long start12 = System.currentTimeMillis();
System.out.println(start12 - start11);long start21 = System.currentTimeMillis();
for (int i = 0; i < 1000; i++) {list2.add(i + 2, i);
}
long start22 = System.currentTimeMillis();
System.out.println(start22 - start21);#输出结果164285

结论：ArrayList比LinkedList慢太多，而且基数越大，ArrayList的耗时成指数级上升！

原因分析：

​ ArrayList需要找到插入的位置index，然后使用System.arraycopy()方法复制index前后的数据,然后让拼接成新的组合数组，然后再删除原先旧的数组

​ LinkedList只需要找到插入的位置index，断开index-1和index+1的连接，然后让index-1指向index，index指向index+1即可

删除性能

按坐标删除

List array = new ArrayList();
List linked = new LinkedList();
for (int i = 0; i < 100000; i++) {array.add(i+"");linked.add(i+"");
}long start1 = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {array.remove(0);
}
long end1 = System.currentTimeMillis();
System.out.println(end1 - start1);long start2 = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {linked.remove(0);
}
long end2 = System.currentTimeMillis();
System.out.println(end2 - start2);#输出结果7616

结论：LinkedList比ArrayList快太多！

按元素删除

List array = new ArrayList();
List linked = new LinkedList();
for (int i = 0; i < 100000; i++) {array.add(i+"");linked.add(i+"");
}
//以下为了更好的理解，不决定引入迭代类删除，所以顶多只能删除一半数据
long start1 = System.currentTimeMillis();
for (int i = 0; i < 50000; i++) {array.remove(i+"");
}
long end1 = System.currentTimeMillis();
System.out.println(end1 - start1);long start2 = System.currentTimeMillis();
for (int i = 0; i < 50000; i++) {linked.remove(i+"");
}
long end2 = System.currentTimeMillis();
System.out.println(end2 - start2);#输出结果6648

结论：LinkedList比ArrayList快太多！

原因分析：根据结论，无论是按坐标删除还是按集合元素删除，LinkedList都比ArrayList快太多！原因很简单，ArrayList删除一个元素意味着这个列表中剩余的元素都会被移动，特别是从集合第一个元素开始删除时，N-1个元素都得位移，而LinkedList只需要改变指向关系即可，特别是集合第一个元素，甚至都不需要改变指向关系，只需要让index为1的标记为新的index为0的头元素

修改性能

List array = new ArrayList();
List linked = new LinkedList();
for (int i = 0; i < 100000; i++) {array.add(i);linked.add(i+"");
}
long start1 = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {array.set(i,i+1);
}
long end1 = System.currentTimeMillis();
System.out.println(end1 - start1);long start2 = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {linked.set(i,i+1);
}
long end2 = System.currentTimeMillis();
System.out.println(end2 - start2);#输出结果49429

结论：ArrayList比LinkedList快太多！

原因分析：ArrayList对于随机的set操作，通过二分查找下标进行value替换；LinkedList需要按照顺序从列表的一端开始检查，直到另外一端!

查询性能

List list1 = new ArrayList();
List list2 = new LinkedList();
for (int i = 0; i < 100000; i++) {list1.add(i);list2.add(i);
}long start11 = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {list1.get(i);
}
long start12 = System.currentTimeMillis();
System.out.println(start12 - start11);long start21 = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {list2.get(i);
}
long start22 = System.currentTimeMillis();
System.out.println(start22 - start21);#输出结果15634

结论：ArrayList查询比LinkedList快太多！

原因分析：与修改性能原因分析一样!

HashMap和Hashtable

插一句，隔空问以下Hashtable命名的作者，你是认真的吗？还是觉得它的父类Dictionary已经被废弃了，就这么随意命名了啊？但这又涉及到一个先后顺序啊，未必作者还能未卜先知？

线程安全性

package com.paratera.console.dict.utils;import java.util.HashMap;
import java.util.Hashtable;
import java.util.Map;public class Test {static Map map = new HashMap();static Map table = new Hashtable();public static void main(String[] args) throws InterruptedException {ThreadTask threadTask1 = new ThreadTask(map);ThreadGroup threadGroup1 = new ThreadGroup("hashMapTest");for (int i = 0; i < 10; i++) {Thread thread1 = new Thread(threadGroup1,threadTask1);thread1.start();}while (threadGroup1.activeCount() != 0){}System.out.println("mapSize为：" + map.size());ThreadTask threadTask2 = new ThreadTask(table);ThreadGroup threadGroup2 = new ThreadGroup("hashTableTest");for (int i = 0; i < 10; i++) {Thread thread2 = new Thread(threadGroup2,threadTask2);thread2.start();}while (threadGroup2.activeCount() != 0){}System.out.println("tableSize为：" + table.size());}
}class ThreadTask implements Runnable {private Map<String, Integer> map;public ThreadTask(Map map) {this.map = map;}@Overridepublic void run() {for(int i = 0; i < 100; i++) {map.put(Thread.currentThread().getName() + i, i);}}
}#输出结果mapSize为：901tableSize为：1000

结论：HashMap线程不安全，并发操作时key会被覆盖，Hashtable线程安全！

原因分析：Hashtable的put方法被synchronized关键字修饰，实现了同步锁

HashMap线程安全加持

synchronize

class ThreadTask implements Runnable {private Map<String, Integer> map;public ThreadTask(Map map) {this.map = map;}@Overridepublic synchronized void run() {for(int i = 0; i < 100; i++) {map.put(Thread.currentThread().getName() + i, i);}}
}#在上面线程类run方法上加synchronized锁住执行
#输出结果mapSize为：1000tableSize为：1000

结论：HashMap线程操作实现了并发线程安全！

原因分析：其实就是synchronized+Hashtable的效果

ConcurrentHashMap

static Map map = new ConcurrentHashMap();

结论：HashMap线程操作实现了并发线程安全！

原因分析：分段锁技术，首先将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问----实现了线程安全，也兼容了性能!

HashMap、Hashtable，synchronize、ConcurrentHashMap

HashSet与TreeSet

性能对比

新增

Set hash = new HashSet();
Set tree = new TreeSet();
long start1 = System.currentTimeMillis();
for (int i = 0; i < 1000000; i++) {hash.add(i);
}
long end1 = System.currentTimeMillis();
System.out.println(end1-start1);long start2 = System.currentTimeMillis();
for (int i = 0; i < 1000000; i++) {tree.add(i);
}
long end2 = System.currentTimeMillis();
System.out.println(end2-start2);#输出结果151393

结论：HashSet比TreeSet快！

原因分析：HashSet使用hash值的地址机制来存储信息的（散列法），元素并没有以某种特定顺序来存放；提供一个使用树结构存储Set接口的实现(红黑树算法)，对象以升序顺序存储

查询

Set hash = new HashSet();
Set tree = new TreeSet();
for (int i = 0; i < 10000000; i++) {hash.add(i);tree.add(i);
}
long start1 = System.currentTimeMillis();
Iterator iterator1 = hash.iterator();
while (iterator1.hasNext()) {iterator1.next();
}
long end1 = System.currentTimeMillis();
System.out.println(end1 - start1);long start2 = System.currentTimeMillis();
Iterator iterator2 = tree.iterator();
while (iterator2.hasNext()) {iterator2.next();
}
long end2 = System.currentTimeMillis();
System.out.println(end2 - start2);#输出结果920359

结论：HashSet比TreeSet慢！

原因分析：存储的性能优点同时是查询的短板，反之也成立

功能对比

• HashSet

@Data
class Student implements Comparable<Student> {private String name;private int age;public Student(String name, int age) {this.name = name;this.age = age;}@Overridepublic int compareTo(Student o) {int num = this.age - o.age;return num == 0 ? this.name.compareTo(o.name): num;}
}public static void main(String[] args) throws InterruptedException {Set<Student> ts = new HashSet<Student>();Student s1 = new Student("xishi", 29);Student s2 = new Student("wangzhaojun", 28);Student s3 = new Student("diaochan", 30);Student s4 = new Student("yangyuhuan", 33);ts.add(s1);ts.add(s2);ts.add(s3);ts.add(s4);for (Student s : ts) {System.out.println(s.getName() + ", " + s.getAge());}
}#输出结果xishi, 29yangyuhuan, 33diaochan, 30wangzhaojun, 28

• TreeSet

#仅仅将set换成TreeSet
Set<Student> ts = new TreeSet<Student>();#输出结果wangzhaojun, 28xishi, 29diaochan, 30yangyuhuan, 33

结论：TreeSet拥有HashSet所有功能外，还具有排序功能

原因分析：HashSet使用hash值的地址机制来存储信息的（散列法），元素并没有以某种特定顺序来存放；提供一个使用树结构存储Set接口的实现(红黑树算法)，对象以升序顺序存储

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！