Skip to content

Commit 9fb3bdb

Browse files
yangqccyangqcc
committed
HashMap,TreeMap,HashTable区别
1 parent 46e445d commit 9fb3bdb

13 files changed

Lines changed: 417 additions & 94 deletions

‎src/main/java/basic/collection/map/HashTableTest.java‎

Lines changed: 74 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,74 @@
1+
package basic.collection.map;
2+
3+
import java.util.*;
4+
import java.util.concurrent.ConcurrentHashMap;
5+
6+
/**
7+
* <p>title:</p>
8+
* <p>description:
9+
* Hashtable和HashMap的区别
10+
* Hashtable不同于HashMap，前者既不允许key为null，也不允许value为null;
11+
* <p>
12+
* HashMap中用于定位桶位的Key的hash的计算过程要比Hashtable复杂一点，没有Hashtable如此简单、直接；
13+
* <p>
14+
* 在HashMap的插入K/V对的过程中，总是先插入后检查是否需要扩容；而Hashtable则是先检查是否需要扩容后插入；
15+
* <p>
16+
* Hashtable不同于HashMap，前者的put操作是线程安全的。
17+
* </p>
18+
*
19+
* @author yangqc
20+
* @date Created in 2019-05-13
21+
* @modified By yangqc
22+
*/
23+
public class HashTableTest {
24+
25+
public static void main(String[] args) {
26+
Hashtable<Integer, Integer> hashTable = new Hashtable<>();
27+
hashTable.put(1, 2);
28+
29+
TreeMap<TestNoCompare, Integer> treeMap = new TreeMap<>();
30+
/**
31+
* treeMap的键要么实现Comparable接口，要么传入一个Comparator
32+
*/
33+
treeMap.put(new TestNoCompare("12"), 2);
34+
Set<Map.Entry<TestNoCompare, Integer>> entries = treeMap.entrySet();
35+
Iterator<Map.Entry<TestNoCompare, Integer>> iterator = entries.iterator();
36+
while (iterator.hasNext()) {
37+
System.out.println(iterator.next());
38+
}
39+
40+
41+
/**
42+
* 第三个参数是顺序，true是获取顺序，false是插入顺序
43+
* LinkedHashMap可以用来做LRU算法实现
44+
*/
45+
LinkedHashMap<Integer, Integer> linkedHashMap = new LinkedHashMap<>(12, 0.75f, true);
46+
linkedHashMap.put(12, 21);
47+
linkedHashMap.get(12);
48+
49+
ConcurrentHashMap<Integer, Integer> concurrentHashMap = new ConcurrentHashMap<>(12);
50+
concurrentHashMap.put(1, 2);
51+
System.out.println(concurrentHashMap.get(1));
52+
}
53+
}
54+
55+
class TestNoCompare implements Comparable<TestNoCompare> {
56+
private String name;
57+
58+
public TestNoCompare(String name) {
59+
this.name = name;
60+
}
61+
62+
public String getName() {
63+
return name;
64+
}
65+
66+
public void setName(String name) {
67+
this.name = name;
68+
}
69+
70+
@Override
71+
public int compareTo(TestNoCompare o) {
72+
return 0;
73+
}
74+
}

‎src/main/java/basic/collection/map/SimpleHashMap.java‎

Lines changed: 62 additions & 65 deletions
Original file line numberDiff line numberDiff line change
@@ -1,83 +1,80 @@
11
package basic.collection.map;
22

3-
import java.util.AbstractMap;
4-
import java.util.HashSet;
5-
import java.util.LinkedList;
6-
import java.util.ListIterator;
7-
import java.util.Set;
3+
import java.util.*;
84

95
/**
106
* @author yangqc
117
*/
128
public class SimpleHashMap<K, V> extends AbstractMap<K, V> {
139

14-
static final int SIZE = 997;
10+
static final int SIZE = 997;
1511

16-
@SuppressWarnings("unchecked")
17-
LinkedList<MapEntry<K, V>>[] buckets = new LinkedList[SIZE];
12+
@SuppressWarnings("unchecked")
13+
LinkedList<MapEntry<K, V>>[] buckets = new LinkedList[SIZE];
1814

19-
@Override
20-
public V put(K key, V value) {
21-
V oldValue = null;
22-
int index = Math.abs(key.hashCode()) % SIZE;
23-
if (buckets[index] == null) {
24-
buckets[index] = new LinkedList<>();
15+
@Override
16+
public V put(K key, V value) {
17+
V oldValue = null;
18+
int index = Math.abs(key.hashCode()) % SIZE;
19+
if (buckets[index] == null) {
20+
buckets[index] = new LinkedList<>();
21+
}
22+
LinkedList<MapEntry<K, V>> bucket = buckets[index];
23+
MapEntry<K, V> pair = new MapEntry<>(key, value);
24+
boolean found = false;
25+
ListIterator<MapEntry<K, V>> it = bucket.listIterator();
26+
while (it.hasNext()) {
27+
MapEntry<K, V> iPair = it.next();
28+
if (iPair.getKey().equals(key)) {
29+
oldValue = iPair.getValue();
30+
it.set(pair);
31+
found = true;
32+
break;
33+
}
34+
}
35+
if (!found) {
36+
buckets[index].add(pair);
37+
}
38+
return oldValue;
2539
}
26-
LinkedList<MapEntry<K, V>> bucket = buckets[index];
27-
MapEntry<K, V> pair = new MapEntry<>(key, value);
28-
boolean found = false;
29-
ListIterator<MapEntry<K, V>> it = bucket.listIterator();
30-
while (it.hasNext()) {
31-
MapEntry<K, V> iPair = it.next();
32-
if (iPair.getKey().equals(key)) {
33-
oldValue = iPair.getValue();
34-
it.set(pair);
35-
found = true;
36-
break;
37-
}
38-
}
39-
if (!found) {
40-
buckets[index].add(pair);
41-
}
42-
return oldValue;
43-
}
4440

45-
public V get(Object key) {
46-
int index = Math.abs(key.hashCode()) % SIZE;
47-
if (buckets[index] == null) {
48-
return null;
49-
}
50-
for (MapEntry<K, V> iPair : buckets[index]) {
51-
if (iPair.getKey().equals(key)) {
52-
return iPair.getValue();
53-
}
41+
@Override
42+
public V get(Object key) {
43+
int index = Math.abs(key.hashCode()) % SIZE;
44+
if (buckets[index] == null) {
45+
return null;
46+
}
47+
for (MapEntry<K, V> iPair : buckets[index]) {
48+
if (iPair.getKey().equals(key)) {
49+
return iPair.getValue();
50+
}
51+
}
52+
return null;
5453
}
55-
return null;
56-
}
5754

58-
@Override
59-
public Set<Entry<K, V>> entrySet() {
60-
Set<Entry<K, V>> set = new HashSet<>();
61-
for (LinkedList<MapEntry<K, V>> bucket : buckets) {
62-
if (bucket == null) {
63-
continue;
64-
}
65-
for (MapEntry<K, V> mpair : bucket) {
66-
set.add(mpair);
67-
}
55+
@Override
56+
public Set<Entry<K, V>> entrySet() {
57+
Set<Entry<K, V>> set = new HashSet<>();
58+
for (LinkedList<MapEntry<K, V>> bucket : buckets) {
59+
if (bucket == null) {
60+
continue;
61+
}
62+
for (MapEntry<K, V> mpair : bucket) {
63+
set.add(mpair);
64+
}
65+
}
66+
return set;
6867
}
69-
return set;
70-
}
7168

72-
public static void main(String[] args) {
73-
SimpleHashMap<String, String> m = new SimpleHashMap<>();
74-
m.put("123", "dsadcds");
75-
m.put("2", "dw");
76-
Set<Entry<String, String>> set = m.entrySet();
77-
for (Entry<String, String> entry : set) {
78-
System.out.println(entry.getValue());
69+
public static void main(String[] args) {
70+
SimpleHashMap<String, String> m = new SimpleHashMap<>();
71+
m.put("123", "dsadcds");
72+
m.put("2", "dw");
73+
Set<Entry<String, String>> set = m.entrySet();
74+
for (Entry<String, String> entry : set) {
75+
System.out.println(entry.getValue());
76+
}
77+
System.out.println(m);
78+
System.out.println(m.get("123"));
7979
}
80-
System.out.println(m);
81-
System.out.println(m.get("123"));
82-
}
8380
}

‎src/main/java/basic/collection/map/package-info.java‎

Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
package basic.collection.map;
2+
3+
/**
4+
* LinkedHashMap实现LRU是需要基础LinkedHashMap,然后重写removeEldestEntry
5+
*
6+
* void addEntry(int hash, K key, V value, int bucketIndex) {
7+
* <p>
8+
* super.addEntry(hash, key, value, bucketIndex);
9+
* <p>
10+
* <p>
11+
* <p>
12+
* // Remove eldest entry if instructed
13+
* <p>
14+
* Entry<K,V> eldest = header.after;
15+
* <p>
16+
* if (removeEldestEntry(eldest)) {
17+
* <p>
18+
* removeEntryForKey(eldest.key);
19+
* <p>
20+
* }
21+
* <p>
22+
* }
23+
* <p>
24+
* 在增加Entry的时候，通过removeEldestEntry(eldest)判断是否需要删除最老的Entry，如果需要则remove。
25+
* 注意看这里Entry<K,V> eldest=header.after，记得我们前面提过LinkedHashMap还维护一个双向链表，这里的header.after就是链表尾部最后一个元素(头部元素是head.before)。
26+
* <p>
27+
* LinkedHashMap默认的removeEldestEntry方法如下
28+
* <p>
29+
* protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
30+
* <p>
31+
* return false;
32+
* <p>
33+
* }
34+
* <p>
35+
* 总是返回false，所以开发者需要实现LRU算法只需要继承LinkedHashMap并重写removeEldestEntry方法，下面以MyBatis的LRU算法的实现举例
36+
* <p>
37+
* keyMap = new LinkedHashMap<Object, Object>(size, .75F, true) {
38+
* <p>
39+
* private static final long serialVersionUID = 4267176411845948333L;
40+
* <p>
41+
* <p>
42+
* <p>
43+
* protected boolean removeEldestEntry(Map.Entry<Object, Object> eldest) {
44+
* <p>
45+
* boolean tooBig = size() > size;
46+
* <p>
47+
* if (tooBig) {
48+
* <p>
49+
* eldestKey = eldest.getKey();
50+
* <p>
51+
* }
52+
* <p>
53+
* return tooBig;
54+
* <p>
55+
* }
56+
* <p>
57+
* };
58+
*/

‎src/main/java/basic/thread/aqs/CountDownLatchTest.java‎

Lines changed: 7 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -7,18 +7,20 @@
77
/**
88
* <p>title:CountDownLatch测试</p>
99
* <p>description:
10-
* ①某一线程在开始运行前等待n个线程执行完毕。将 CountDownLatch 的计数器初始化为n ：new CountDownLatch(n) ， 每当一个任务线程执行完毕，就将计数器减1
11-
* countdownlatch.countDown()，当计数器的值变为0时，在CountDownLatch上 await() 的线程就会被唤醒。
10+
* ①某一线程在开始运行前等待n个线程执行完毕。将 CountDownLatch 的计数器初始化为n ：new CountDownLatch(n) ，每当一个任务线程执行完毕，就将计数器减1
11+
* CountDownLatch.countDown()，当计数器的值变为0时，在CountDownLatch上 await() 的线程就会被唤醒。
1212
* 一个典型应用场景就是启动一个服务时，主线程需要等待多个组件加载完毕，之后再继续执行。
1313
* <p>
14-
* ②实现多个线程开始执行任务的最大并行性。注意是并行性，不是并发，强调的是多个线程在某一时刻同时开始执行。 类似于赛跑，将多个线程放到起点，等待发令枪响，然后同时开跑。做法是初始化一个共享的
15-
* CountDownLatch 对象，将其计数器初始化为 1 ：new CountDownLatch(1) ，多个线程在开始执行任务前首先 coundownlatch.await()，当主线程调用
14+
* ②实现多个线程开始执行任务的最大并行性。注意是并行性，不是并发，强调的是多个线程在某一时刻同时开始执行。
15+
* 类似于赛跑，将多个线程放到起点，等待发令枪响，然后同时开跑。做法是初始化一个共享的
16+
* CountDownLatch 对象，将其计数器初始化为 1 ：new CountDownLatch(1) ，多个线程在开始执行任务前首先 CountDownLatch.await()，当主线程调用
1617
* countDown() 时，计数器变为0，多个线程同时被唤醒。
1718
* <p>
1819
* ③死锁检测：一个非常方便的使用场景是，你可以使用n个线程访问共享资源，在每次测试阶段的线程数目是不同的，并尝试产生死锁。
1920
* </p>
2021
* <p>
21-
* CountDownLatch的不足： CountDownLatch是一次性的，计数器的值只能在构造方法中初始化一次，之后没有任何机制再次对其设置值，当CountDownLatch使用完毕后，它不能再次被使用。
22+
* CountDownLatch的不足： CountDownLatch是一次性的，计数器的值只能在构造方法中初始化一次，之后没有任何机制再次对其设置值，
23+
* 当CountDownLatch使用完毕后，它不能再次被使用。
2224
*
2325
* @author yangqc
2426
* @date Created in 2019-04-13

‎src/main/java/basic/thread/aqs/CyclicBarrierTest.java‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -12,7 +12,8 @@
1212
* <p>
1313
* CyclicBarrier 的应用场景
1414
* <p>
15-
* CyclicBarrier 可以用于多线程计算数据，最后合并计算结果的应用场景。比如我们用一个Excel保存了用户所有银行流水， 每个Sheet保存一个帐户近一年的每笔银行流水，现在需要统计用户的日均银行流水，
15+
* CyclicBarrier 可以用于多线程计算数据，最后合并计算结果的应用场景。比如我们用一个Excel保存了用户所有银行流水，
16+
* 每个Sheet保存一个帐户近一年的每笔银行流水，现在需要统计用户的日均银行流水，
1617
* 先用多线程处理每个sheet里的银行流水，都执行完之后，得到每个sheet的日均银行流水，最后，再用barrierAction用这些线程的计算结果，计算出整个Excel的日均银行流水。
1718
* </p>
1819
*
@@ -48,8 +49,7 @@ public static void test1() {
4849
}
4950

5051
public static void test2() throws InterruptedException {
51-
CyclicBarrier cyclicBarrier = new CyclicBarrier(5, () ->
52-
{
52+
CyclicBarrier cyclicBarrier = new CyclicBarrier(5, () -> {
5353
try {
5454
Thread.sleep(1000);
5555
System.out.println("线程到达数量后，优先执行!");

‎src/main/java/basic/thread/forkjoin/CountTask.java‎

Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,65 @@
1+
package basic.thread.forkjoin;
2+
3+
import java.util.concurrent.ForkJoinPool;
4+
import java.util.concurrent.ForkJoinTask;
5+
import java.util.concurrent.RecursiveTask;
6+
7+
/**
8+
* <p>title:</p>
9+
* <p>description:</p>
10+
*
11+
* @author yangqc
12+
* @date Created in 2019-05-08
13+
* @modified By yangqc
14+
*/
15+
public class CountTask extends RecursiveTask<Long> {
16+
17+
/**
18+
* 阈值
19+
*/
20+
private static final int THRESHOLD = 1000;
21+
22+
private long start;
23+
24+
private long end;
25+
26+
public CountTask(long start, long end) {
27+
this.start = start;
28+
this.end = end;
29+
}
30+
31+
@Override
32+
protected Long compute() {
33+
long sum = 0;
34+
//阈值小于1000就不分解了
35+
boolean canCompute = (end - start) < THRESHOLD;
36+
if (canCompute) {
37+
for (long i = start; i <= end; i++) {
38+
sum += i;
39+
}
40+
} else {
41+
long middle = (start + end) / 2;
42+
CountTask leftTask = new CountTask(start, middle);
43+
CountTask rightTask = new CountTask(middle, end);
44+
leftTask.fork();
45+
rightTask.fork();
46+
long leftResult = leftTask.join();
47+
long rightResult = rightTask.join();
48+
//合并任务
49+
sum = leftResult + rightResult;
50+
}
51+
return sum;
52+
}
53+
54+
public static void main(String[] args) {
55+
ForkJoinPool forkJoinPool = new ForkJoinPool();
56+
CountTask task = new CountTask(0, 200000L);
57+
ForkJoinTask<Long> result = forkJoinPool.submit(task);
58+
try {
59+
long res = result.get();
60+
System.out.println("sum=" + res);
61+
} catch (Exception e) {
62+
e.printStackTrace();
63+
}
64+
}
65+
}

0 commit comments

Comments
 (0)