logo

Java - Collections

Last Updated: 2021-11-19

Java 7 vs Java 8: HashMap

HashMap collision: if two entries have the same key, they will be saved internally as follows

  • Java 7: use LinkedList, will be slow if there are too many collisions
  • Java 8: use red-black tree

Using Java 8 HashMaps buckets with too

Suppose we have a Person class defined and may have the following operations:

Map<Person, String> map = new HashMap<>();
map.put(person, “value");
map.get(person);

In Java 8:

  • If there are too many entries under the same bucket, it will be tree-fied once a threshold value is met.
  • If Person is comparable, it will be much faster.
@Override
public int compareTo(Person person) {
    return this.id.compareTo(person.id);
}

Sort Map

public static <K, V extends Comparable<V>> List<Map.Entry<K,V>> getEntriesSortedByValues(Map<K,V> map){
    List<Map.Entry<K,V>> entries = new LinkedList<Map.Entry<K,V>>(map.entrySet());

    Collections.sort(entries, new Comparator<Map.Entry<K,V>>() {

        public int compare(Entry<K, V> o1, Entry<K, V> o2) {
            return o1.getValue().compareTo(o2.getValue());
        }
    });

    return entries;
}

The right way to print an array

System.out.println(Arrays.toString(arr));

Increment Count

private void incMapCnt(Map<String, Integer> map, String key) {
    int cnt = map.containsKey(key) ? map.get(key) : 0;
    map.put(key, cnt + 1);
}

Set Operation

Union

Set<Type> union = new HashSet<>(s1);
union.addAll(s2);

Intersection

Set<Type> intersection = new HashSet<>(s1);
intersection.retainAll(s2);

Differences

Set<Type> difference = new HashSet<>(s1);
difference.removeAll(s2);

Unique and duplicates

Set<String> uniques = new HashSet<>();
Set<String> dups    = new HashSet<>();

for (String a : args)
    if (!uniques.add(a))
        dups.add(a);

// Destructive set-difference
uniques.removeAll(dups);

Set<Type> symmetricDiff = new HashSet<>(s1);
symmetricDiff.addAll(s2);
Set<Type> tmp = new HashSet<>(s1);
tmp.retainAll(s2));
symmetricDiff.removeAll(tmp);

Array to list:

List<String> list = Arrays.asList(args);

Initialize Array/List

Arrays.asList(1, 2, 3, 4, 5)
new Integer[]{1, 2, 3, 4, 5}

Arrays.asList() UnsupportedOperationException

Arrays.asList() is a convenient way to create a List by literals:

List<Integer> l = Arrays.asList(0,1,2);

Arrays.asList() returns a fixed-size list that does not support any structural modification(add or remove).

list.add(3);

This will throw UnsupportedOperationException

Caused by: java.lang.UnsupportedOperationException
	at java.util.AbstractList.add(AbstractList.java:131)
	at java.util.AbstractList.add(AbstractList.java:91)

Workaround:

List<Integer> list = new ArrayList<>(Arrays.asList(0));

LinkedListNode

static class LinkedListNode<E> {
    E data;
    LinkedListNode<E> next;
}

null in HashSet

null can be a unique value in a HashSet, and can be printed out:

@Test
public void testNullInSet() {
    Set<String> set = new HashSet<>();
    Assert.assertFalse(set.contains(null));
    set.add(null);
    Assert.assertTrue(set.contains(null));
    System.out.println(set);
}
[null]

Convert Array to String

String[] arr = new String[]{"foo", "bar"};

Array derives from Object, so there's a toString(), however it does not print the content but the hash: [Ljava.lang.String;@48f2f70c

String s = arr.toString();

Use Arrays.toString() instead: [foo, bar]

String s = Arrays.toString(arr);

To quoted Strings: ["foo","bar"]

ObjectMapper objectMapper = new ObjectMapper();
String s = objectMapper.writeValueAsString(arr);

Multi-dimension Array, use Arrays.deepToString()

String[][] arr = new String[][]{{"foo1", "bar1"}, {"foo2", "bar2"}};
System.out.println(Arrays.deepToString(arr));
//[[foo1, bar1], [foo2, bar2]]

Array vs List

String[] is a subset of Object[]:

System.out.println(String[].class);
//class [Ljava.lang.String;

System.out.println(String[].class.isAssignableFrom(Object[].class));
//false

System.out.println(Object[].class.isAssignableFrom(String[].class));
//true

String[] values = new String[]{"a", "b", "c"};

System.out.println(values instanceof String[]);
System.out.println(values instanceof Object[]);

However List<String> is NOT a subset of List<Object>.

Assume we have testList:

private void testList(List<Object> values) {}

this will cause compile error:

@Test
public void test() {
    List<String> stringList = Arrays.asList("a", "b", "c");
    testList(stringList);
}

Compile Error:
    required: java.util.List<java.lang.Object>
    found: java.util.List<java.lang.String>

This is ok:

private void testArray(Object[] values) {}

@Test
public void test() {
    String[] stringArray = new String[]{"a", "b", "c"};
    testArray(stringArray);
}

List to Array

List<String> x = ...
x.toArray()

though x is List<String>, toArray() will return Object[], to return String[]:

String[] y = x.toArray(new String[0]);

Collections.unmodifiableList vs ImmutableList

  • Collections.unmodifiableList accepts null
  • ImmutableList(Guava) rejects null

HashMap vs. Map

A: Map is Interface, Hashmap is the class implements Map

HashMap vs. Hashtable

  • HashMap: not synchronized; permit NULL; order may change.
  • Hashtable: synchronized; not permit NULL; constant order.

Vector vs ArrayList

  • Vector is synchronized; ArrayList is not.

Array vs ArrayList

Array

  • Fixed length
  • can be primitive types

ArrayList

  • Auto expands
  • Object only, no primitive types, use wrapper classes(Integer, Double, Character)

HashMap

In the version 8 of Java, the Collection HashMap has been modified such that instead of using a LinkedList to store different elements with colliding hashcodes, a Red-Black tree is used. This results in the improvement of time complexity of searching such an element from O(n) to O(log n)