Map Implementations

[toc]

The Java HashMap Under the Hood

1
2


A Guide to TreeMap in Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
TreeMap<Integer, String> treeMap = new TreeMap<>(Comparator.reverseOrder());
treeMap.put(1, "a");
treeMap.put(2, "a");
treeMap.put(3, "a");
treeMap.put(4, "a");
treeMap.put(5, "a");

System.out.println(treeMap.lastKey());
System.out.println(treeMap.firstKey());
System.out.println(treeMap.headMap(3).keySet().toString());
System.out.println(treeMap.tailMap(3).keySet().toString());
//1
//5
//[5, 4]
//[3, 2, 1]

Java TreeMap vs HashMap

  1. Differences
    1. Implementation
      红黑树 hashtable
    1. Order
    1. Null Values
      不允许 null 作为 key 允许 null 作为 key
  2. Performance Analysis
    3.1. HashMap
    3.2. TreeMap
  3. Similarities
    4.1. Unique Elements
    4.2. Concurrent Access
    Both Map implementations aren’t synchronized
    We have to explicitly use Collections.synchronizedMap(mapName) to obtain a synchronized view of a provided map.
    4.3. Fail-Fast Iterators

Guide to WeakHashMap in Java

WeakHashMap 的用途?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// 2. Strong, Soft, and Weak References
// 2.1. Strong References
Integer prime = 1;

// 2.2. Soft References
// an object that has a SoftReference pointing to it won't be garbage collected until the JVM absolutely needs memory.
Integer prime = 1;
SoftReference<Integer> soft = new SoftReference<Integer>(prime);
prime = null;
// The prime object has a strong reference pointing to it.
// Next, we are wrapping prime strong reference into a soft reference. After making that strong reference null, a prime object is eligible for GC but will be collected only when JVM absolutely needs memory.

// 2.3. Weak References
// The objects that are referenced only by weak references are garbage collected eagerly; the GC won't wait until it needs memory in that case.
Integer prime = 1;
WeakReference<Integer> soft = new WeakReference<Integer>(prime);
prime = null;
// When we made a prime reference null, the prime object will be garbage collected in the next GC cycle, as there is no other strong reference pointing to it.

// 3. WeakHashMap as an Efficient Memory Cache
// References of a WeakReference type are used as keys in WeakHashMap.
WeakHashMap<UniqueImageName, BigImage> map = new WeakHashMap<>();
BigImage bigImage = new BigImage("image_id");
UniqueImageName imageName = new UniqueImageName("name_of_big_image");

map.put(imageName, bigImage);
assertTrue(map.containsKey(imageName));

imageName = null;
System.gc();

await().atMost(10, TimeUnit.SECONDS).until(map::isEmpty);

A Guide to ConcurrentMap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 2. ConcurrentMap   是一个 interface
// Several default implementations are overridden, disabling the null key/value support:
getOrDefault
forEach
replaceAll
computeIfAbsent
computeIfPresent
compute
merge
// The following APIs are also overridden to support atomicity, without a default interface implementation:
putIfAbsent
remove
replace(key, oldValue, newValue)
replace(key, value)

// 3. ConcurrentHashMap
// 3.1. Thread-Safety
// 3.2. Null Key/Value
// 3.3. Stream Support
// 3.4. Performance
// 3.5. Pitfalls
// 4. ConcurrentNavigableMap
// 5. ConcurrentSkipListMap

Guide to the ConcurrentSkipListMap

1
2


An Introduction to Java.util.Hashtable Class

1
2


A Guide to LinkedHashMap in Java

1
2


A Guide to EnumMap

1
2


Immutable Map Implementations in Java

1
2


A Guide to Java HashMap

1
2


Set Implementations

[toc]

A Guide to TreeSet in Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// 2. Intro to TreeSet
// 2.1. TreeSet With a Constructor Comparator Param
Set<String> treeSet = new TreeSet<>(Comparator.comparing(String::length));
// 2.2 synchronized treeSet
Set<String> syncTreeSet = Collections.synchronizedSet(treeSet);
// 3. TreeSet add()
// 返回 boolean, 源码如下,可以看到内部用的是 treemap
public boolean add(E e) {
return m.put(e, PRESENT) == null;
}
// 4. TreeSet contains()
// 5. TreeSet remove() 返回 boolean
// 6. TreeSet clear()
// 7. TreeSet size()
// 8. TreeSet isEmpty()
// 9. TreeSet iterator()--升序 descendingIterator()--降序
// 若迭代时用treeSet 的 remove 方法,会触发 fail-fast 机制,抛出 ConcurrentModificationException 异常
while (itr.hasNext()) {
itr.next();
treeSet.remove("Second");
}
// 但是若用 Iterator 的 remove 方法就没问题
while (itr.hasNext()) {
String element = itr.next();
if (element.equals("Second"))
itr.remove();
}

// 10. TreeSet first()
// size() 为 0 的话抛出异常
// 11. TreeSet last()
// 12. TreeSet subSet()
// return the elements ranging from fromElement to toElement
// 13. TreeSet headSet()
// return elements of TreeSet which are smaller than the specified element:
// 14. TreeSet tailSet()
// return the elements of a TreeSet which are greater than or equal to the specified element
// 15. Storing Null Elements
// 不可添加 null

A Guide to HashSet in Java

内部维护了一个 HashMap

How HashSet Maintains Uniqueness?

When we put an object into a HashSet, it uses the object’s hashcode value to determine if an element is not in the set already.

Each hash code value corresponds to a certain bucket location which can contain various elements, for which the calculated hash value is the same. But two objects with the same *hashCode* might not be equal.

So, objects within the same bucket will be compared using the equals() method.

List Operations

[toc]

Converting Iterator to List

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 有时会获得一个 Iterator
Iterator<Integer> iterator = Arrays.asList(1, 2, 3).iterator();
// 怎么转成 List 呢
List<Integer> actualList = new ArrayList<>();
// 1. using a while loop
while (iterator.hasNext()) {
actualList.add(iterator.next());
}
// 2. using java 8 Iterator.forEachRemaining
iterator.forEachRemaining(actualList::add);
// 3. using java 8 streams API ?
// 先把 iterator 转成 iterable
Iterable<Integer> iterable = () -> iterator;
List<Integer> actualList = StreamSupport
.stream(iterable.spliterator(), false)
.collect(Collectors.toList());
// 4. Guava
// 4.1 Immutable List
List<Integer> actualList = ImmutableList.copyOf(iterator);
// 4.2 mutable list
List<Integer> actualList = Lists.newArrayList(iterator);
// 5. apache Commons
List<Integer> actualList = IteratorUtils.toList(iterator);

assertThat(actualList, containsInAnyOrder(1, 2, 3));

Java – Get Random Item/Element From a List

1
2
3
4
5
6
7
8
9
10
11
List<Integer> givenList = Arrays.asList(1, 2, 3);
// 2.1. Single Random Item
Random rand = new Random();
givenList.get(rand.nextInt(givenList.size()));
// 2.2. in Multithread Environment
int randomElementIndex = THreadLocalRandom.current().nextInt(listSize) % givenList.size();
// 2.4. Without Repetitions
// 获取后 remove 元素即可
givenList.remove(randomIndex);
// 2.5. Select Random Series
Collections.shuffle(givenList);

Partition a List in Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// 将一个 list 划分为指定长度的 sublists
List<Integer> intList = Lists.newArrayList(1, 2, 3, 4, 5, 6, 7, 8, 9); // guava
// 1. Guava
// Keep in mind that the partitions are sublist views of the original collection
// which means that changes in the original collection will be reflected in the partitions
// 1.1. Use Guava to Partition the List
Lists.partition(intList, 3);
// 1.2. Use Guava to partition a Collection
// 略
// 2. Use Apache Commons Collections to Partition the List
// the same caveat applies here as well –
// the resulting partition are views of the original List.
ListUtils.partition(intList, 3);
// 3. Use Java8 to Partition the List
// 3.1. Collectors partitioningBy
// use Collectors.partitioningBy() to split the list into 2 sublists
Map<Boolean, List<Integer>> groups =
intList.stream().collect(Collectors.partitioningBy(s -> s > 6));
List<List<Integer>> subSets = new ArrayList<List<Integer>>(groups.values());
// 3.2. Collectors groupingBy
// use Collectors.groupingBy() to split our list to multiple partitions
Map<Integer, List<Integer>> groups =
intList.stream().collect(Collectors.groupingBy(s -> (s - 1) / 3));
List<List<Integer>> subSets = new ArrayList<List<Integer>>(groups.values());
// 3.3. Split the List by Separator
// use Java8 to split our List by separator
int[] indexes = Stream.of(IntStream.of(-1), IntStream.range(0, intList.size())
.filter(i -> intList.get(i) == 0), IntStream.of(intList.size()))
.flatMapToInt(s -> s).toArray();
List<List<Integer>> subSets = IntStream.range(0, indexes.length - 1)
.mapToObj(i -> intList.subList(indexes[i] + 1, indexes[i + 1]))
.collect(Collectors.toList());

Removing all nulls from a List in Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
List<Integer> list = Lists.newArrayList(null, 1, null);
// 1. plain java
while (list.remove(null));
// 或者
list.removeAll(Collections.singleton(null)); // ?
// 2. Guava
// 2.1 via predicates (modify original list)
Iterables.removeIf(list, Predicates.isNull());
// 2.2 do not modify original list
List<Integer> listWithoutNulls = Lists.newArrayList(
Iterables.filter(list, Predicates.notNull()));
assertThat(list, hasSize(1));
// 3. Commons
// (modify original list)
CollectionUtils.filter(list, PredicateUtils.notNullPredicate());
// 4. java8 lambdas
// 4.1 parallel (do not modify original list)
list.parallelStream()
.filter(Objects::nonNull)
.collect(Collectors.toList());
// 4.2 serial (do not modify original list)
list.stream()
.filter(Objects::nonNull)
.collect(Collectors.toList());
// 4.3 (modify original list)
list.removeIf(Objects::isNull);

Removing all duplicates from a List in Java

1
2
3
4
5
6
7
8
9
10
11
List<Integer> list = Lists.newArrayList(0, 1, 2, 3, 0, 0);
// 以下做法均类似于 Python 的 list(set(l))
// 1. plain java
// using set
List<Integer> listWithoutDuplicates = new ArrayList<>(new HashSet<>(list));
// 2. Guava
Lists.newArrayList(Sets.newHashSet(list));
// 3. java 8 stream
list.stream().distinct().collect(Collectors.toList());

assertThat(listWithoutDuplicates, hasSize(4));

Check If Two Lists are Equal in Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
List<String> list1 = Arrays.asList("1", "2", "3", "4");
List<String> list2 = Arrays.asList("1", "2", "3", "4");
List<String> list3 = Arrays.asList("1", "2", "4", "3");
// 1. JUnit
Assert.assertEquals(list1, list2);
Assert.assertNotSame(list1, list2);
Assert.assertNotEquals(list1, list3);
// 2. TestNG (用法类似)
Assert.assertEquals(list1, list2);
Assert.assertNotSame(list1, list2);
Assert.assertNotEquals(list1, list3);
// 3. AssertJ
assertThat(list1)
.isEqualTo(list2)
.isNotEqualTo(list3);
assertThat(list1.equals(list2)).isTrue;
assertThat(list1.equals(list3)).isFalse;

How to Find an Element in a List with Java

1
2
3
4
5
6
7
8
9
10
11
12
13
// contains indexOf loop
// 略
// java 8 stream api
// invoke stream() on the list
// call the filter() method with a proper Predicate
// call the findAny() construct which returns the first element
// that matches the filter predicate wrapped in an Optional if such an element exists
customers.stream()
.filter(customer -> "James".equals(customer.getName()))
.findAny()
.orElse(null);
// guava / commons
// 写的很晦涩,略

Java List UnsupportedOperationException

1
2
3
4
List<String> flowerList = Arrays.asList(flowers);
// Arrays.asList() 返回的 list 大小固定,不可增删(修改呢?)
// 改进, 若要修改
new ArrayList(Arrays.asList(flowers));

Copy a List to Another List in Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 1. 利用构造函数

List<Integer> copy = new ArrayList<>(list);
// 2. addAll
List<Integer> copy = new ArrayList<>();
copy.addAll(list);
// 但是: 这 2 种方法只是复制了引用,修改一个会影响另一个

// 3. Collections.copy
// src dest 长度一样,dest 会被覆盖
List<Integer> source = Arrays.asList(1,2,3);
List<Integer> dest = Arrays.asList(4,5,6);
Collections.copy(dest, source);
// dest 留出前三个位置
List<Integer> source = Arrays.asList(1, 2, 3);
List<Integer> dest = Arrays.asList(5, 6, 7, 8, 9, 10);
Collections.copy(dest, source);

// 4. java 8 stream
list.stream().collect(Collectors.toList());

Remove All Occurrences of a Specific Value from a List

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
// list.remove(1) 若 1 是 int, 会被当成索引,不是 value,是 integer 才行
// void removeAll(List<Integer> list, int element) {
void removeAll(List<Integer> list, Integer element) {
while (list.contains(element)) {
list.remove(element);
}
}
// 或者
void removeAll(List<Integer> list, Integer element) {
int index;
while ((index = list.indexOf(element)) >= 0) {
list.remove(index);
}
}

// 但以上方法都很慢
// for loop, 但需要考虑到同时删除相邻元素时的问题
// 因此,因为 for-each loop 没有解决同时删除相邻元素时的问题,test failed
void removeAll(List<Integer> list, int element) {
for (int i = 0; i < list.size();) {
if (Objects.equals(element, list.get(i))) {
list.remove(i);
} else {
i++;
}
}
}
// using an Iterator
void removeAll(List<Integer> list, int element) {
for (Iterator<Integer> i = list.iterator(); i.hasNext();) {
Integer number = i.next();
if (Objects.equals(number, element)) {
i.remove();
}
}
}
// 建立一个新 list
List<Integer> removeAll(List<Integer> list, int element) {
List<Integer> remainingElements = new ArrayList<>();
for (Integer number : list) {
if (!Objects.equals(number, element)) {
remainingElements.add(number);
}
}
return remainingElements;
}
// 或者返回 void
void removeAll(List<Integer> list, int element) {
List<Integer> remainingElements = new ArrayList<>();
for (Integer number : list) {
if (!Objects.equals(number, element)) {
remainingElements.add(number);
}
}

list.clear();
list.addAll(remainingElements);
}
// stream api
list.stream().filter(e -> !Object.equals(e, element))
.collect(Collectors.toList());

// 最简单的方法(你不早说):
// removeIf
list.removeIf(n -> Objects.equals(n, element));

Add Multiple Items to an Java ArrayList

1
2
3
4
5
6
7
8
// list1.addAll(list2)   
// Collections.addAll(list1, list2)
// Collections.addAll(list1, 1, 2, 3)
// 以上 2 种方法添加的都是引用

// using stream 更简便,还能用 skip filter
source.stream().forEachOrdered(target::add);
// 不能用collect(target::add) ,因为 collect 将所有元素看为一个整体

Remove the First Element from a List

1
2
3
4
// ArrayList
list.remove(0);
// linkedList
list.removeFirst()

Ways to Iterate Over a List in Java

1
2
3
4
5
// loop foreach loop Iterator
// list.forEach
countries.forEach(System.out::println);
// Stream.forEach()
countries.stream().forEach((c) -> System.out.println(c));

Intersection of Two Lists in Java

1
2
3
4
5
List<String> list = Arrays.asList("red", "blue", "blue", "green", "red");
List<String> otherList = Arrays.asList("red", "green", "green", "yellow");

Set<String> result = list.stream().filter(otherList::contains)
.collect(Collectors.toSet());

:D 一言句子获取中...