Comment écrire le code d'implémentation de la collection Java

1, HashMap

public class HashMapDemo {
    private Map map = null;
    public void init() {
        map = new HashMap();
        map.put("a", "aaa");
        map.put("b", "bbb");
        map.put("c", "ccc");
        System.out.println(map);
    }
    // 添加元素
    public void testPut() {
        // V put(K key, V value) ：把指定的key和value添加到集合中
        map.put("a1", "aaa");
        map.put("b1", "bbb");
        map.put("c1", "ccc");
        System.out.println(map);
        // void putAll(Map<? extends K,? extends V>m) ：把指定集合添加集合中
        Map map1 = new HashMap();
        map1.put("e", "eee");
        map1.put("f", "fff");
        map.putAll(map1);
        System.out.println(map);
        // default V putIfAbsent(K key, V value) ：如果key不存在就添加
        map.putIfAbsent("a", "hello");
        System.out.println(map);
        map.putIfAbsent("g", "ggg");
        System.out.println(map);
    }
    // 修改元素
    public void testModify() {
        // V put(K key, V value) ：把集合中指定key的值修改为指定的值
        map.put("a", "hello");
        map.put("a", "world");
        System.out.println(map);
        // 说明，当key相同时，后面的值会覆盖前面的值。
        // default V replace(K key, V value) ：根据key来替换值，而不做增加操作
        Object replace = map.replace("b1", "java");
        System.out.println(replace);
        System.out.println(map);
        //default boolean replace(K key, V oldValue,V newValue)
    }
    // 删除元素
    public void testRemove() {
        // V remove(Object key) ：根据指定key删除集合中对应的值
        Object c = map.remove("c");
        System.out.println(c);
        System.out.println(map);
        // default boolean remove(Object key, Objectvalue) ：根据key和value进行删除
        map.remove("b", "bbb1");
        System.out.println(map);
        // void clear() ：清空集合中所有元素
        map.clear();
        System.out.println(map);
    }
    // 判断元素
    public void testJudge() {
        // boolean isEmpty() ：判断集合是否为空，如果是返回true，否则返回false
        System.out.println(map.isEmpty());
        // boolean containsKey(Object key) ：判断集合中是否包含指定的key，包含返回true，否则返回false
        boolean flag = map.containsKey("a");
        System.out.println(flag); // true
        flag = map.containsKey("a1");
        System.out.println(flag); // false
        // boolean containsValue(Object value) ：判断集合中是否包含指定的value，包含返回true，否则返回false
        flag = map.containsValue("aaa");
        System.out.println(flag); // true
        flag = map.containsValue("aaa1");
        System.out.println(flag); // false
    }
    // 获取元素
    public void testGet() {
        // int size() ：返回集合的元素个数
        int size = map.size();
        System.out.println(size);
        // V get(Object key) ：根据Key获取值，如果找到就返回对应的值，否则返回null
        Object val = map.get("a");
        System.out.println(val);
        val = map.get("a1");
        System.out.println(val); // null
        // default V getOrDefault(Object key, VdefaultValue) ：根据Key获取值，如果key不存在，则返回默认值
        val = map.getOrDefault("a1", "hello");
        System.out.println(val);
        // Collection<V> values() ：返回集合中所有的Value
        Collection values = map.values();
        for (Object value : values) {
            System.out.println(value);
        }
        // Set<K> keySet() ：返回集合中所有的Key
        Set set = map.keySet();
        for (Object o : set) {
            System.out.println(o);
        }
    }
    // 迭代元素
    public void testIterator() {
        // 第一种：通过key获取值的方式
        Set keySet = map.keySet();
        Iterator it = keySet.iterator();
        while (it.hasNext()) {
            Object key = it.next();
            Object val = map.get(key);
            System.out.println(key + "=" + val);
        }
        System.out.println("------------------------ ");
        // 第二种：使用for循环
        for (Object key : map.keySet()) {
            System.out.println(key + "=" +
                               map.get(key));
        }
        System.out.println("------------------------ ");
        // 第三种：使用Map接口中的内部类来完成，在框架中大量使用
        Set entrySet = map.entrySet();
        for (Object obj : entrySet) {
            Map.Entry entry = (Map.Entry) obj;
            System.out.println(entry.getKey() + "=" +
                               entry.getValue());
        }
    }
}

Remarque : Dans HashMap, la valeur-clé peut être vide, mais la clé est unique et la valeur peut être répétée. hashMap n'est pas thread-safe.

2. TreeMap

est un ensemble ordonné, et la valeur par défaut est la méthode de tri naturel.

public class Person implements Comparable {
    private String name;
    private int age;
    @Override
    public int compareTo(Object o) {
    if (o instanceof Person) {
    Person p = (Person) o;
    return this.age - p.age;
    }
    return 0;
}
    public Person() {}
    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }
    public int getAge() {
        return age;
    }
    public void setAge(int age) {
        this.age = age;
    }
    @Override
    public String toString() {
        return "Person{" +
            "name='" + name + '\'' +
            ", age=" + age +
            '}';
    }
}

test

public class TeeMapDemo {
    @Test
    public void testInteger() {
        TreeMap tm = new TreeMap();
        tm.put(3, 333);
        tm.put(2, 222);
        tm.put(11, 111);
        tm.put(2, 222);
        System.out.println(tm);
    }
    @Test
    public void testString() {
        TreeMap tm = new TreeMap();
        tm.put("hello", "hello");
        tm.put("world", "world");
        tm.put("about", "");
        tm.put("abstract", "");
        System.out.println(tm);
    }
    @Test
    public void testPerson() {
        TreeMap tm = new TreeMap(new Comparator(){
            @Override
            public int compare(Object o1, Object o2) {
                if (o1 instanceof Person && o2
                    instanceof Person) {
                    Person p1 = (Person) o1;
                    Person p2 = (Person) o2;
                    return p1.getAge() - p2.getAge();
                }
                return 0;
            }
        });
        tm.put(new Person("张三",18), null);
        tm.put(new Person("李四",17), null);
        System.out.println(tm);
    }
}

Explication : À partir du code ci-dessus, nous pouvons constater que l'utilisation de TreeMap est très similaire à l'utilisation de TreeSet. En observant le code source du HashSet. collection, nous pouvons voir que lors de la création Lors de la collecte de HashSet, HashMap est en fait utilisé au niveau de la couche inférieure.

public HashSet() {
	map = new HashMap<>();
}

HashSet stocke en fait la clé de HashMap.

3.ConcurrentHashMap

Dans la collection Map nous avons introduit HashMap, TreeMap, dans le cas du multi-threading Aucune de ces collections n'est thread-safe, des problèmes de sécurité des threads peuvent donc survenir. HashMap，TreeMap，在多线程的情况下这些集合都不是线程安全的，因此可能出现线程安全的问题。

在Java中Hashtable是一种线程安全的HashMap，Hashtable在方法上与HashMap并无区别，仅仅只是在方法使用了synchronized以此来达到线程安全的目的，我们观察Hashtable的源码。

public synchronized V get(Object key) {
        Entry<?,?> tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                return (V)e.value;
            }
        }
        return null;
    }

以上是Hashtable的get源码，可以看出它仅仅只是在方法上添加了锁，这大大降低了线程的执行效率，以牺牲效率的形式来达到目的，这显然不是我们在实际中想要的，因此我们需要一种既能在线程安全方面有保障，在效率上还可以的方法。

ConcurrentHashMap采用的是分段锁的原理，我们观察源码。

 public V put(K key, V value) {
        return putVal(key, value, false);
    }
final V putVal(K key, V value, boolean onlyIfAbsent) {
        if (key == null || value == null) throw new NullPointerException();
        int hash = spread(key.hashCode());
        int binCount = 0;
        for (Node<K,V>[] tab = table;;) {
            Node<K,V> f; int n, i, fh;
            if (tab == null || (n = tab.length) == 0)
                tab = initTable();
            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
                if (casTabAt(tab, i, null,
                             new Node<K,V>(hash, key, value, null)))
                    break;                   // no lock when adding to empty bin
            }
            else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab, f);
            else {
                V oldVal = null;
                synchronized (f) {
                    if (tabAt(tab, i) == f) {
                        if (fh >= 0) {
                            binCount = 1;
                            for (Node<K,V> e = f;; ++binCount) {
                                K ek;
                                if (e.hash == hash &&
                                    ((ek = e.key) == key ||
                                     (ek != null && key.equals(ek)))) {
                                    oldVal = e.val;
                                    if (!onlyIfAbsent)
                                        e.val = value;
                                    break;
                                }
                                Node<K,V> pred = e;
                                if ((e = e.next) == null) {
                                    pred.next = new Node<K,V>(hash, key,
                                                              value, null);
                                    break;
                                }
                            }
                        }
                        else if (f instanceof TreeBin) {
                            Node<K,V> p;
                            binCount = 2;
                            if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                           value)) != null) {
                                oldVal = p.val;
                                if (!onlyIfAbsent)
                                    p.val = value;
                            }
                        }
                    }
                }
                if (binCount != 0) {
                    if (binCount >= TREEIFY_THRESHOLD)
                        treeifyBin(tab, i);
                    if (oldVal != null)
                        return oldVal;
                    break;
                }
            }
        }
        addCount(1L, binCount);
        return null;
    }

从源码中可以看出ConcurrentHashMap

En Java, Hashtable est un HashMap thread-safe. Il n'y a aucune différence de méthode entre Hashtable et HashMap. . , en utilisant simplement synchronized dans la méthode pour assurer la sécurité des threads, nous observons le code source de Hashtable.

rrreee

Ce qui précède est le code source get de Hashtable. On peut voir qu'il ne fait qu'ajouter un verrou à la méthode, ce qui réduit considérablement l'efficacité d'exécution du thread et atteint l'objectif au détriment de. l'efficacité. Ce n'est évidemment pas ce que nous voulons en pratique, nous avons donc besoin d'une méthode à la fois thread-safe et efficace. #🎜🎜##🎜🎜#ConcurrentHashMap utilise le principe du verrouillage segmenté Observons le code source. #🎜🎜#rrreee#🎜🎜# Il ressort du code source que ConcurrentHashMap n'ajoute un verrou que lorsqu'un thread exploite les données actuelles, ce qui améliore considérablement l'efficacité. #🎜🎜##🎜🎜# Efficacité améliorée tout en étant thread-safe. #🎜🎜#

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!