哈希存储

2022-08-05 21:53:42 浏览数 (1)

HashMap 类

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

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

HashMap 构造方法

代码语言：javascript复制
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 类。

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

LinkedHashMap 构造方法

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

代码语言：javascript复制
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 移动到双向链表的表尾。

代码语言：javascript复制
Map<String,Integer> map = new LinkedHashMap<>(32，0.5f, true);    // 基于访问顺序排序Copy to clipboardErrorCopied

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

代码语言：javascript复制
// 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 类提供了以下专属方法使用。

代码语言：javascript复制
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 接口

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

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

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

遍历顺序

List / Queue 接口
  • 全部方法：按数组或链表顺序输出。
Map / Set 接口
  • HashSet/HashMap 类：在返回数据时没有特别的顺序。
  • LinkedHashSet/LinkedHashMap 类：默认按插入顺序返回数据，也可以按访问顺序返回。
  • TreeSet/TreeMap 类：在返回数据时按 key 值从小到大排列，即按照树的中序遍历返回。

遍历方法

Collection 接口
代码语言：javascript复制
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 接口
代码语言：javascript复制
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

遍历失败

在迭代元素的时候不能通过集合的方法修改或删除元素，但可以通过迭代器的 remove 方法删除元素。

  • java.util 包下面的所有的集合类都是快速失败的。直接对原容器进行修改，会抛出 ConcurrentModificationException 异常。
  • java.util.concurrent 包下面的所有的集合类都是安全失败的。遍历时先对底层集合做拷贝再遍历，因此不会抛出异常。
hashmap 容器 编程算法 网站 存储

0 人点赞