哈希存储

Qwe7

发布于 2022-08-05 21:53:42

54400

代码可运行

文章被收录于专栏：网络收集网络收集

运行总次数：0

代码可运行

HashMap 类

【哈希表】实现 Map 接口。底层使用散列存储：构造一个 Entry 数组，根据 key 的 hash 值将 Entry 存入指定位置。

key 值无序且不可重复，且允许 null 作为 key 值存在。
发生哈希冲突时，HashMap 采用链表保存多个元素。当链表长度大于 8 时，链表自动转化为红黑树。
达到负载因数后，HashMap 将调用 resize 方法动态扩容：新建一个 2 倍容量的新数组复制当前数组的数据。

HashMap 构造方法

Map<String,Integer> map = new HashMap<>();                       // 默认初始容量 16 负载因数 0.75
Map<String,Integer> map = new HashMap<>(32);                     // 自定义初始容量
Map<String,Integer> map = new HashMap<>(32, 0.5f);               // 自定义初始容量和负载因数Copy to clipboardErrorCopied

LinkedHashMap 类

【链式哈希表】继承 HashMap 类。

底层使用散列存储：构造一个 Entry 数组，根据 key 的 hash 值将 Entry 存入指定位置。
Entry 额外添加了引用 before & after ，使哈希表内的所有 Entry 构成一个双向链表维护 Entry 的顺序。

LinkedHashMap 构造方法

在默认情况下 Entry 按照插入顺序排序，可指定创建时的初始容量和负载因数。

Map<String,Integer> map = new LinkedHashMap<>();                  // 默认初始容量 16 负载因数 0.75 
Map<String,Integer> map = new LinkedHashMap<>(32);                // 自定义初始容量
Map<String,Integer> map = new LinkedHashMap<>(32, 0.5f);          // 自定义初始容量和负载因数Copy to clipboardErrorCopied

Entry 也可以按照访问顺序排序：对 Entry 进行操作时会先删除再插入，将 Entry 移动到双向链表的表尾。

Map<String,Integer> map = new LinkedHashMap<>(32，0.5f, true);    // 基于访问顺序排序Copy to clipboardErrorCopied

LinkedHashMap 类提供了 removeEldestEntry 方法，在使用 put 操作插入 Entry 时将自动调用此方法决定是否移除双向链表表头的 Entry：默认返回 false ，可通过重写此方法以实现 LRU 算法。

// Entry 超过容量后自动删除最久未使用的 Entry
Map<String,Integer> map = new LinkedHashMap<>(capacity, 0.5f, true){
    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {  
        return size() > capacity;  
    }  
};Copy to clipboardErrorCopied

TreeMap 类

【树表】实现了 Map 接口。底层使用红黑树存储：Entry 按照 key 值大小插入红黑树，并动态调整红黑树高度。

TreeMap 类方法

TreeMap 类提供了以下专属方法使用。

map.firstKey();                   // 返回最小 key
map.lastKey();                    // 返回最大 key

map.ceilingKey("10");             // 返回大于等于10的最小 Key，不存在则返回 null
map.ceilingEntry("10");           // 返回大于等于10的最小 Key 的键值对(getKey / getValue 方法)

map.floorKey("10");               // 返回小于等于10的最大 Key，不存在则返回 null
map.floorEntry("10");             // 返回小于等于10的最大 Key 的键值对Copy to clipboardErrorCopied

Set 子类

HashSet 类：【散列集】基于 HashMap 类实现。
LinkedHashSet 类：【链式散列集】基于 LinkedHashMap 类实现。
TreeSet 类：【树集】基于 TreeMap 类实现。

元素遍历

遍历容器

Iterable 接口

是集合框架的顶级接口，被所有容器类都实现。

提供 iterator 方法，用来创建一个实现了 Iterator 接口的 iterator 对象：按容器类规定的顺序实现遍历集合。
JDK 1.8 引入 foreach 方法遍历集合。效率更高，但不能对元素进行删除操作，否则会抛出异常。

Iterator 接口

提供了 hasNext、next、remove 三个方法，可以按容器类规定的顺序实现遍历集合。

遍历顺序

List / Queue 接口

全部方法：按数组或链表顺序输出。

Map / Set 接口

HashSet/HashMap 类：在返回数据时没有特别的顺序。
LinkedHashSet/LinkedHashMap 类：默认按插入顺序返回数据，也可以按访问顺序返回。
TreeSet/TreeMap 类：在返回数据时按 key 值从小到大排列，即按照树的中序遍历返回。

遍历方法

Collection 接口

List<String> list = new ArrayList<>();

// iterator 遍历
Iterator<Integer> iter = list.iterator();
while(iter.hasNext()){              
      int num = iter.next();
      if(num < 0) iter.remove();
}

// 随机遍历（效率更高，但不能进行删除操作）
for (String str : list) {
      System.out.println(str);
}Copy to clipboardErrorCopied

Map 接口

Map<String,String> map=new HashMap<String,String>();

// iterator 遍历
Iterator<Map.Entry<String, String>> iter = map.entrySet().iterator(); 
while (iter.hasNext()) { 
    Map.Entry<String, String> entry = iter.next(); 
    System.out.println(entry.getKey() + entry.getValue()); 
} 

// 随机遍历（效率更高，但不能进行删除操作）
for (Map.Entry<String, String> entry : map.entrySet()) { 
    System.out.println(entry.getKey() + entry.getValue()); 
} 

// 只遍历 key
for (String key : map.keySet()) { 
    System.out.println(key + map.get(key)); 
} 

// 只遍历 value
for (String value : map.values()) { 
    System.out.println(value); 
}Copy to clipboardErrorCopied