search
HomeJavajavaTutorialJava Programming Thoughts Learning Class (4) Chapter 17 - In-depth Discussion of Containers

1 Set and storage order

  • #The elements added to SetmustDefine the equals() method to ensure the uniqueness of the object.

  • hashCode()Only when this class is placed in HashSet or LinkedHashSet is what is necessary. But as a matter of good programming style, you should always override the hashCode() method when overriding the equals() method.

  • If an object is used in any kind of sorted container, such as SortedSet(TreeSet is its only implementation), then it must implement the Comparable interface.

  • Note that SortedSet means "according to the comparison function of the object Sorting" rather than "the order in which elements are inserted". Insertion orderUse LinkedHashSet to save.

2 Queue

  • For concurrent applications, the only two implementations of Queue in Java SE5 are LinkedList and PriorityQueue, they only have sorting behavior differences, there is no difference in performance.

  • The order of priority queue PriorityQueue is also controlled by implementing Comparable.

3 Map

Map table (also called associative arrayAssociative Array).

3.1 Performance

HashMap uses a special value, called hash code (hash code), to Replaces slow searches for keys. A hash code is a "relatively unique"int value used to represent an object. It is performed by combining certain information about the object. Generated by converting .
hashCode() is a method in the root class Object, so all objects can generate hash codes.

The requirements for keys used in a Map are the same as for the elements in a Set:

  • Any key must have an equals( )Method;

  • If the key is used to hash the Map, it must also have the appropriate hashCode()Method;

  • If the key is used for TreeMap, then it must implement Comparable.

4 Hash and Hash Code

HashMap uses equals() to determine whether the current key is consistent with the table The same keys exist.
  The default Object.equals() just compares the address of the object . If you want to use your own class as the key of HashMap , you must override both hashCode() and equals().
  The correct equals() method must meet the following 5 conditions:

  • Reflexivity.

  • symmetry.

  • Transitivity.

  • consistency.

  • For any x that is not null, x.equals(null) must return false.

4.1 The concept of hashing

The purpose of using hashing is: You want to use one object to find another object.
  The implementation class of Map uses hashing to increase the query speed.

The value of hashing is speed: Hashing allows queries to be performed quickly. Since the bottleneck is query speed, one solution is to keep the keys sorted and then use Collections.binarySearch() to query.

Hashing goes one step further and saves the key somewhere so that it can be found quickly. The fastest data structure to store a set of elements is an array, so use it to represent the key information (note carefully that I mean the key information, not the key itself). But because the array cannot adjust its capacity, there is a problem: we want to save an uncertain number of values ​​in the Map, but what if the number of keys is limited by the capacity of the array?

The answer is: The array does not save the key itself. Instead, a number is generated from the key object and used as the subscript of the array. This number is the hash code, determined by the hashCode() method defined in Object and possibly overridden by your class. (called a hash function in computer science terms) is generated.

To solve the problem of fixed array capacity, different keys can produce the same subscript. That is, there may be conflicts, i.e. the hash codes do not have to be unique. Therefore, it doesn't matter how big the array is, any key will always find its place in the array.

4.2 Understanding hashing

To sum up, Hash is to generate a number from an object and save it (as the bottom of the array) standard), and then just find the number directly when searching for this object, so the purpose of hashing is to improve the search speed, and the means is to combine the number generated by an object with its Associated and saved (through an array, called a hash table). The generated number is the hash code. The method of generating this hash code is called hash function (hashCode()).

4.3 HashMap query process (quick reason)

  Therefore, the process of querying a key in HashMap is:

  • First calculate the hash code

  • Then use the hash code to query the array (the hash code is used as the variable array subscript)

  • If there is no conflict, that is, there is only one object that generates this hash code, then the position of the array subscript corresponding to the hash code is the element to be found

  • If there is a conflict, then scatter The array element where the subscript corresponding to the column code is located saves a list, and then use the equals() method to perform a linear query on the values ​​in list.

## therefore, instead of querying the entire

list, quickly jump to a certain position in the array, only for very few The elements are compared . This is why HashMap is so fast.

4.4 Implementation of Simple Hash Map

  • The

    slot (slot) in the hash table is usually called the bucket bit(bucket)

  • To make the hash even, the number of buckets usually uses

    prime numbers(It is a prime number in JDK5, and it is already an integer of 2 in JDK7 Powered ).

    It turns out that prime numbers are not actually the ideal capacity for a hash bucket. Recently, Java's hash functions (through extensive testing) use
    2 raised to the integer power. Division and remainder are the slowest operations on modern processors. Using a hash table with an integer power of 2 length, mask can be used instead of division. Because get() is the most commonly used operation, the % operation of finding the remainder is the most expensive part, and using the integer power of 2 can eliminate this overhead (it may also have some impact on hashCode()).
  • The get() method calculates the index in the buckets array in the same way as the put() method. This is important because it ensures that both methods can calculate

    Same location .

  • package net.mrliuli.containers;
    
    import java.util.*;public class SimpleHashMap<K, V> extends AbstractMap<K, V> {    // Choose a prime number for the hash table size, to achieve a uniform distribution:
        static final int SIZE = 997;    // You can&#39;t have a physical array of generics, but you can upcast to one:
        @SuppressWarnings("unchecked")
        LinkedList<MapEntry<K,V>>[] buckets = new LinkedList[SIZE];
    
        @Override    public V put(K key, V value){        int index = Math.abs(key.hashCode()) % SIZE;        if(buckets[index] == null){
                buckets[index] = new LinkedList<MapEntry<K,V>>();
            }
    
            LinkedList<MapEntry<K,V>> bucket = buckets[index];
            MapEntry<K,V> pair = new MapEntry<K,V>(key, value);
    
            boolean found = false;
            V oldValue = null;
            ListIterator<MapEntry<K,V>> it = bucket.listIterator();        while(it.hasNext()){
                MapEntry<K,V> iPair = it.next();            if(iPair.equals(key)){
                    oldValue = iPair.getValue();
                    it.set(pair); // Replace old with new
                    found = true;                break;
                }
            }        if(!found){
                buckets[index].add(pair);
            }        return oldValue;
        }
    
        @Override    public V get(Object key){        int index = Math.abs(key.hashCode()) % SIZE;        if(buckets[index] == null) return null;        for(MapEntry<K,V> iPair : buckets[index]){            if(iPair.getKey().equals(key)){                return iPair.getValue();
                }
            }        return null;
        }
    
        @Override    public Set<Map.Entry<K,V>> entrySet(){
            Set<Map.Entry<K,V>> set = new HashSet<Map.Entry<K, V>>();        for(LinkedList<MapEntry<K,V>> bucket : buckets){            if(bucket == null) continue;            for(MapEntry<K,V> mpair : bucket){                set.add(mpair);
                }
            }        return set;
        }    public static void main(String[] args){
            SimpleHashMap<String, String> m = new SimpleHashMap<String, String>();        for(String s : "to be or not to be is a question".split(" ")){
                m.put(s, s);
                System.out.println(m);
            }
            System.out.println(m);
            System.out.println(m.get("be"));
            System.out.println(m.entrySet());
        }
    }
4.5 Overriding hashCode()

 Factors to consider when designing `hashCode()`:

  • The most important Factors:

    Whenever , calling hashCode() on the same phase object should produce the same value.

  • In addition, hashCode() should not be made to rely on unique object information, especially using the value of this, which can only produce a very bad hashCode(). Because this cannot generate a new key that is the same as the key in the original key-value pair in put(). That is, the

    meaningful identification information within the object should be used. That is, it must generate a hash code based on the content of the object.

  • However, the identity of the object must be completely determined through hashCode() equals().

  • Because hashCode() requires further processing before generating the bucket's subscript, the generation range of the hash code does not matter, as long as it is an int.

  • Good hashCode() should produce evenly distributed hash codes.

"Effective Java™ Programming Language Guide (Addison-Wesley, 2001)" gives a basic guide on how to write a decent hashCode():

  1. Assign a non-zero value constant to the

    int variable result, such as 17

  2. 为对象内每个有意义的域f(即每个可以做equals()操作的域)计算出一个int散列码c

域类型 计算
boolean c=(f?0:1)
byte、char、short或int c=(int)f
long c=(int)(f^(f>>>32))
float c=Float.floatToIntBits(f);
double long l = Double.doubleToLongBits(f);
Object,其equals()调用这个域的equals() c=f.hashCode()
数组 对每个元素应用上述规则

3. 合并计算散列码:result = 37 * result + c;
4. 返回result。
5. 检查hashCode()最后生成的结果,确保相同的对象有相同的散列码。

5 选择不同接口的实现

5.1 微基准测试的危险(Microbenchmarking dangers)

已证明0.0是包含在Math.random()的输出中的,按照数学术语,即其范围是[0,1)

5.2 HashMap的性能因子

  HashMap中的一些术语:

  • 容量(Capacity):表中的桶位数(The number of buckets in the table)。

  • 初始容量(Initial capacity):表在创建时所拥有的桶位数。HashMapHashSet都具有允许你指定初始容量的构造器。

  • 尺寸(Size):表中当前存储的项数。

  • 负载因子(Loadfactor):尺寸/容量。空表的负载因子是0,而半满表的负载因子是0.5,依此类推。负载轻的表产生冲突的可能性小,因此对于插入和查找都是最理想的(但是会减慢使用迭代器进行遍历的过程)。HashMapHashSet都具有允许你指定负载因子的构造器,表示当负载情况达到该负载的水平时,容器将自动增加其容量(桶位数),实现方式是使容量大致加倍,并重新将现有对象分布到新的桶位集中(这被称为再散列)。

HashMap使用的默认负载因子是0.75(只有当表达到四分之三满时,才进行再散列),这个因子在时间和空间代价之间达到了平衡。更高的负载因子可以降低表所需的空间,但会增加查找代价,这很重要,因为查找是我们在大多数时间里所做的操作(包括get()put())。

6 Collection或Map的同步控制

  Collections类有办法能够自动同步整个容器。其语法与“不可修改的”方法相似:

package net.mrliuli.containers;

import java.util.*;public class Synchronization {    public static void main(String[] args){
        Collection<String> c = Collections.synchronizedCollection(new ArrayList<String>());
        List<String> list = Collections.synchronizedList(new ArrayList<String>());        Set<String> s = Collections.synchronizedSet(new HashSet<String>());        Set<String> ss = Collections.synchronizedSortedSet(new TreeSet<String>());
        Map<String, String> m = Collections.synchronizedMap(new HashMap<String, String>());
        Map<String, String> sm = Collections.synchronizedSortedMap(new TreeMap<String, String>());
    }
}

6.1 快速报错(fail-fast)

  Java容器有一种保护机制能够防止多个进行同时修改同一个容器的内容。Java容器类类库采用快速报错(fail-fast)机制。它会探查容器上的任何除了你的进程所进行的操作以外的所有变化,一旦它发现其他进程修改了容器,就会立刻抛出ConcurrentModificationException异常。这就是“快速报错”的意思——即,不是使用复杂的算法在事后来检查问题。

package net.mrliuli.containers;
import java.util.*;public class FailFast {    public static void main(String[] args){
        Collection<String> c = new ArrayList<>();
        Iterator<String> it = c.iterator();
        c.add("An Object");        try{
            String s = it.next();
        }catch(ConcurrentModificationException e){
            System.out.println(e);
        }
    }
}

相关文章:

Java编程思想学习课时(三)第15章-泛型

Java编程思想学习课时(五)第18章-Java IO系统

The above is the detailed content of Java Programming Thoughts Learning Class (4) Chapter 17 - In-depth Discussion of Containers. For more information, please follow other related articles on the PHP Chinese website!

Statement
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
带你搞懂Java结构化数据处理开源库SPL带你搞懂Java结构化数据处理开源库SPLMay 24, 2022 pm 01:34 PM

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于结构化数据处理开源库SPL的相关问题,下面就一起来看一下java下理想的结构化数据处理类库,希望对大家有帮助。

Java集合框架之PriorityQueue优先级队列Java集合框架之PriorityQueue优先级队列Jun 09, 2022 am 11:47 AM

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于PriorityQueue优先级队列的相关知识,Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列,PriorityQueue是线程不安全的,PriorityBlockingQueue是线程安全的,下面一起来看一下,希望对大家有帮助。

完全掌握Java锁(图文解析)完全掌握Java锁(图文解析)Jun 14, 2022 am 11:47 AM

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于java锁的相关问题,包括了独占锁、悲观锁、乐观锁、共享锁等等内容,下面一起来看一下,希望对大家有帮助。

一起聊聊Java多线程之线程安全问题一起聊聊Java多线程之线程安全问题Apr 21, 2022 pm 06:17 PM

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于多线程的相关问题,包括了线程安装、线程加锁与线程不安全的原因、线程安全的标准类等等内容,希望对大家有帮助。

详细解析Java的this和super关键字详细解析Java的this和super关键字Apr 30, 2022 am 09:00 AM

本篇文章给大家带来了关于Java的相关知识,其中主要介绍了关于关键字中this和super的相关问题,以及他们的一些区别,下面一起来看一下,希望对大家有帮助。

Java基础归纳之枚举Java基础归纳之枚举May 26, 2022 am 11:50 AM

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于枚举的相关问题,包括了枚举的基本操作、集合类对枚举的支持等等内容,下面一起来看一下,希望对大家有帮助。

java中封装是什么java中封装是什么May 16, 2019 pm 06:08 PM

封装是一种信息隐藏技术,是指一种将抽象性函式接口的实现细节部分包装、隐藏起来的方法;封装可以被认为是一个保护屏障,防止指定类的代码和数据被外部类定义的代码随机访问。封装可以通过关键字private,protected和public实现。

归纳整理JAVA装饰器模式(实例详解)归纳整理JAVA装饰器模式(实例详解)May 05, 2022 pm 06:48 PM

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于设计模式的相关问题,主要将装饰器模式的相关内容,指在不改变现有对象结构的情况下,动态地给该对象增加一些职责的模式,希望对大家有帮助。

See all articles

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

AI Hentai Generator

AI Hentai Generator

Generate AI Hentai for free.

Hot Article

R.E.P.O. Energy Crystals Explained and What They Do (Yellow Crystal)
2 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
Repo: How To Revive Teammates
1 months agoBy尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: How To Get Giant Seeds
4 weeks agoBy尊渡假赌尊渡假赌尊渡假赌

Hot Tools

mPDF

mPDF

mPDF is a PHP library that can generate PDF files from UTF-8 encoded HTML. The original author, Ian Back, wrote mPDF to output PDF files "on the fly" from his website and handle different languages. It is slower than original scripts like HTML2FPDF and produces larger files when using Unicode fonts, but supports CSS styles etc. and has a lot of enhancements. Supports almost all languages, including RTL (Arabic and Hebrew) and CJK (Chinese, Japanese and Korean). Supports nested block-level elements (such as P, DIV),

SublimeText3 Linux new version

SublimeText3 Linux new version

SublimeText3 Linux latest version

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

PhpStorm Mac version

PhpStorm Mac version

The latest (2018.2.1) professional PHP integrated development tool

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools