KnownCapacityHashMap.java
// Licensed to the Apache Software Foundation (ASF) under one
// or more contributor license agreements. See the NOTICE file
// distributed with this work for additional information
// regarding copyright ownership. The ASF licenses this file
// to you under the Apache License, Version 2.0 (the
// "License"); you may not use this file except in compliance
// with the License. You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing,
// software distributed under the License is distributed on an
// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
// KIND, either express or implied. See the License for the
// specific language governing permissions and limitations
// under the License.
package org.apache.doris.datasource.metacache;
import java.util.AbstractCollection;
import java.util.AbstractMap;
import java.util.AbstractSet;
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Objects;
import java.util.Set;
/**
* An immutable hash map whose retained table and node layouts are known to the size estimator.
*
* <p>Using a private fixed bucket array avoids depending on inaccessible HashMap capacity,
* treeification, cached-view, or serialization behavior. Entries themselves are immutable, so
* iteration does not require allocating an unmodifiable wrapper for every mapping.
*/
public final class KnownCapacityHashMap<K, V> extends AbstractMap<K, V> {
private final Node<K, V>[] table;
private final int size;
private final Set<Entry<K, V>> entrySet;
private final Set<K> keySet;
private final Collection<V> values;
private KnownCapacityHashMap(Map<? extends K, ? extends V> source) {
int tableCapacity = JvmSizeUtils.hashMapTableCapacityForSize(source.size());
table = createTable(tableCapacity);
for (Entry<? extends K, ? extends V> entry : source.entrySet()) {
K key = entry.getKey();
int hash = spreadHash(key);
int index = bucketIndex(hash);
table[index] = new Node<>(hash, key, entry.getValue(), table[index]);
}
size = source.size();
entrySet = Collections.unmodifiableSet(new EntrySet());
keySet = Collections.unmodifiableSet(new KeySet());
values = Collections.unmodifiableCollection(new Values());
}
public static <K, V> KnownCapacityHashMap<K, V> copyOf(Map<? extends K, ? extends V> source) {
return new KnownCapacityHashMap<>(Objects.requireNonNull(source, "source"));
}
int getRetainedTableCapacity() {
return table.length;
}
long getRetainedViewBytes() {
return JvmSizeUtils.saturatedAdd(
JvmSizeUtils.shallowSizeOf(entrySet.getClass()),
JvmSizeUtils.saturatedAdd(
JvmSizeUtils.shallowSizeOf(keySet.getClass()),
JvmSizeUtils.saturatedAdd(
JvmSizeUtils.shallowSizeOf(values.getClass()),
JvmSizeUtils.saturatedAdd(
JvmSizeUtils.shallowSizeOf(EntrySet.class),
JvmSizeUtils.saturatedAdd(
JvmSizeUtils.shallowSizeOf(KeySet.class),
JvmSizeUtils.shallowSizeOf(Values.class))))));
}
@Override
public V get(Object key) {
Node<K, V> node = findNode(key);
return node == null ? null : node.value;
}
@Override
public boolean containsKey(Object key) {
return findNode(key) != null;
}
@Override
public boolean containsValue(Object value) {
for (Node<K, V> bucket : table) {
for (Node<K, V> node = bucket; node != null; node = node.next) {
if (Objects.equals(value, node.value)) {
return true;
}
}
}
return false;
}
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public Set<Entry<K, V>> entrySet() {
return entrySet;
}
@Override
public Set<K> keySet() {
return keySet;
}
@Override
public Collection<V> values() {
return values;
}
private Node<K, V> findNode(Object key) {
if (table.length == 0) {
return null;
}
int hash = spreadHash(key);
for (Node<K, V> node = table[hash & (table.length - 1)]; node != null; node = node.next) {
if (node.hash == hash && Objects.equals(key, node.key)) {
return node;
}
}
return null;
}
private int bucketIndex(int hash) {
return table.length == 0 ? 0 : hash & (table.length - 1);
}
private static int spreadHash(Object key) {
int hash = key == null ? 0 : key.hashCode();
return hash ^ (hash >>> 16);
}
@SuppressWarnings("unchecked")
private static <K, V> Node<K, V>[] createTable(int capacity) {
return (Node<K, V>[]) new Node<?, ?>[capacity];
}
private abstract class ViewIterator<T> implements Iterator<T> {
private int bucketIndex;
private Node<K, V> next;
private ViewIterator() {
advanceBucket();
}
@Override
public boolean hasNext() {
return next != null;
}
@Override
public T next() {
if (next == null) {
throw new NoSuchElementException();
}
Node<K, V> current = next;
next = current.next;
if (next == null) {
advanceBucket();
}
return value(current);
}
@Override
public void remove() {
throw new UnsupportedOperationException("KnownCapacityHashMap is immutable");
}
abstract T value(Node<K, V> node);
private void advanceBucket() {
while (next == null && bucketIndex < table.length) {
next = table[bucketIndex++];
}
}
}
private final class EntrySet extends AbstractSet<Entry<K, V>> {
@Override
public Iterator<Entry<K, V>> iterator() {
return new ViewIterator<Entry<K, V>>() {
@Override
Entry<K, V> value(Node<K, V> node) {
return node;
}
};
}
@Override
public int size() {
return size;
}
}
private final class KeySet extends AbstractSet<K> {
@Override
public Iterator<K> iterator() {
return new ViewIterator<K>() {
@Override
K value(Node<K, V> node) {
return node.key;
}
};
}
@Override
public int size() {
return size;
}
}
private final class Values extends AbstractCollection<V> {
@Override
public Iterator<V> iterator() {
return new ViewIterator<V>() {
@Override
V value(Node<K, V> node) {
return node.value;
}
};
}
@Override
public int size() {
return size;
}
}
private static final class Node<K, V> implements Entry<K, V> {
private final int hash;
private final K key;
private final V value;
private final Node<K, V> next;
private Node(int hash, K key, V value, Node<K, V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
@Override
public K getKey() {
return key;
}
@Override
public V getValue() {
return value;
}
@Override
public V setValue(V value) {
throw new UnsupportedOperationException("KnownCapacityHashMap is immutable");
}
@Override
public boolean equals(Object other) {
if (!(other instanceof Entry)) {
return false;
}
Entry<?, ?> entry = (Entry<?, ?>) other;
return Objects.equals(key, entry.getKey()) && Objects.equals(value, entry.getValue());
}
@Override
public int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
}
}