Hash table (HashMap)
The time complexity of hash query is O(1)
Pass by value
Character, Short, Integer, Long, Float, Double, String, Boolean, in java
the hash table is passed internally in the form of value, not in the form of an address transfer.
For example:
HashMap<Integer, String> intMap = new HashMap<>(); intMap.put(1234567, "111"); Integer a = 1234567; Integer b = 1234567; System.out.println("a==b = " + (a == b)); System.out.println("a.equals(b) = " + a.equals(b)); System.out.println("intMap.get(a) = " + intMap.get(a)); System.out.println("intMap.get(b) = " + intMap.get(b));
// Output result
// a==b = false
// a.equals(b) = true
/ / intMap.get(a) = 111
// intMap.get(b) = 111
In the above case, a!= b
, but intMap.get(a) == intMap.get(b)
. We can see that when we query or operate certain values from the hashmap, they are passed and matched in the form of values, not in the form of Memory address format to match.
Pass by address
If it is a non-native type, it will be passed in the form of a memory address. For example:
public static class Node { private int value; public Node(int value) { this.value = value; } } HashMap<Node, String> map = new HashMap<>(); Node node1 = new Node(1); Node node2 = new Node(1); map.put(node1, "ziop"); System.out.println("map.containsKey(node1) = " + map.containsKey(node1)); System.out.println("map.containsKey(node2) = " + map.containsKey(node2));
//Output result
//map.containsKey(node1) = true
//map.containsKey(node2) = false
Memory size comparison
Basic type, the memory size of a record is the size of the Key plus the size of the Value.
Non-basic type, the memory size of a record is the size of two addresses, one address is 8 bytes, key and value are 16 bytes in total
If it is a basic type and a non-basic type For mixed types, each calculates it in its own way.
Ordered list (TreeMap)
The ordered list will be arranged in ascending order according to the size of the key. We can use It does all the operations in
hashmap
, and extends it to the operation of finding the first key or the last key, as well as the search for the maximum value smaller than a certain interval and larger than a certain interval. The minimum valueThe time complexity of all operations is
O(logn)
level.But if the key is a non-basic type, it cannot be sorted directly. The type needs to implement the sorting interface and have the sorting function. Or pass in the comparison method when new treeMap
Storage basic type operation
TreeMap<Integer, String> treeMap = new TreeMap<>(); treeMap.put(3,"我是3 "); treeMap.put(0,"我是3 "); treeMap.put(7,"我是3 "); treeMap.put(2,"我是3 "); treeMap.put(5,"我是3 "); treeMap.put(9,"我是3 "); treeMap.put(1,"我是3 "); System.out.println("treeMap.containsKey(3) = "+treeMap.containsKey(3)); System.out.println("treeMap.containsKey(6) = "+treeMap.containsKey(6)); System.out.println("treeMap.get(3) = "+treeMap.get(3)); treeMap.put(3,"他是3"); System.out.println("treeMap.get(3) = "+treeMap.get(3)); treeMap.remove(3); System.out.println("treeMap.get(3) = "+treeMap.get(3)); treeMap.remove(3); System.out.println("treeMap.firstKey() = "+treeMap.firstKey()); System.out.println("treeMap.lastKey() = "+treeMap.lastKey()); // 返回 小于等于五 并且最近的 key System.out.println("treeMap.floorKey(5) = "+treeMap.floorKey(5)); System.out.println("treeMap.floorKey(6) = "+treeMap.floorKey(6)); // 返回 大于等于 4 并且最靠近的值 System.out.println("treeMap.ceilingKey(4) = "+treeMap.ceilingKey(4));
//The output result is as follows
//treeMap.containsKey( 3) = true
//treeMap.containsKey(6) = false
//treeMap.get(3) = I am 3
//treeMap.get(3) = He is 3
//treeMap.get(3) = null
//treeMap.firstKey() = 0
//treeMap.lastKey() = 9
//treeMap.floorKey(5) = 5
//treeMap.floorKey(6) = 5
//treeMap.ceilingKey(4) = 5
Storage non-basic types for operations
// 存放非基础类型 public static void main(String[] args) { TreeMap<Node, Integer> treeMap1 = new TreeMap<>(); Node node3 = new Node(3); Node node4 = new Node(4); treeMap1.put(node3, 3); treeMap1.put(node4, 4); System.out.println("treeMap1.firstEntry().getValue() = " + treeMap1.firstEntry().getValue()); System.out.println("treeMap1.lastEntry().getValue() = " + treeMap1.lastEntry().getValue()); } public static class Node implements Comparable<Node> { private int value; public Node(int value) { this.value = value; } @Override public int compareTo(Node node) { return this.value - node.value; } }
The above is the detailed content of How to implement Java hash table and ordered list. For more information, please follow other related articles on the PHP Chinese website!

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

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

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

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

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

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

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

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


Hot AI Tools

Undresser.AI Undress
AI-powered app for creating realistic nude photos

AI Clothes Remover
Online AI tool for removing clothes from photos.

Undress AI Tool
Undress images for free

Clothoff.io
AI clothes remover

AI Hentai Generator
Generate AI Hentai for free.

Hot Article

Hot Tools

WebStorm Mac version
Useful JavaScript development tools

SublimeText3 Mac version
God-level code editing software (SublimeText3)

SublimeText3 Chinese version
Chinese version, very easy to use

Safe Exam Browser
Safe Exam Browser is a secure browser environment for taking online exams securely. This software turns any computer into a secure workstation. It controls access to any utility and prevents students from using unauthorized resources.

Dreamweaver Mac version
Visual web development tools
