hadoop IdentityHashStore 源码

haddop IdentityHashStore 代码

文件路径：/hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/util/IdentityHashStore.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.hadoop.util;

import org.apache.hadoop.classification.InterfaceAudience;
import org.apache.hadoop.classification.InterfaceStability;

/**
 * The IdentityHashStore stores (key, value) mappings in an array.
 * It is similar to java.util.HashTable, but much more lightweight.
 * Neither inserting nor removing an element ever leads to any garbage
 * getting created (assuming the array doesn't need to be enlarged).
 *
 * Unlike HashTable, it compares keys using
 * {@link System#identityHashCode(Object)} and the identity operator.
 * This is useful for types like ByteBuffer which have expensive hashCode
 * and equals operators.
 *
 * We use linear probing to resolve collisions.  This avoids the need for
 * the overhead of linked list data structures.  It also means that it is
 * expensive to attempt to remove an element that isn't there, since we
 * have to look at the entire array to be sure that it doesn't exist.
 *
 * @param <K>    The key type to use.
 * @param <V>    THe value type to use.
 */
@InterfaceAudience.Private
@InterfaceStability.Evolving
@SuppressWarnings("unchecked")
public final class IdentityHashStore<K, V> {
  /**
   * Even elements are keys; odd elements are values.
   * The array has size 1 + Math.pow(2, capacity).
   */
  private Object buffer[];

  private int numInserted = 0;

  private int capacity;

  /**
   * The default maxCapacity value to use.
   */
  private static final int DEFAULT_MAX_CAPACITY = 2;

  public IdentityHashStore(int capacity) {
    Preconditions.checkArgument(capacity >= 0);
    if (capacity == 0) {
      this.capacity = 0;
      this.buffer = null;
    } else {
      // Round the capacity we need up to a power of 2.
      realloc((int)Math.pow(2,
          Math.ceil(Math.log(capacity) / Math.log(2))));
    }
  }

  private void realloc(int newCapacity) {
    Preconditions.checkArgument(newCapacity > 0);
    Object prevBuffer[] = buffer;
    this.capacity = newCapacity;
    // Each element takes two array slots -- one for the key, 
    // and another for the value.  We also want a load factor 
    // of 0.50.  Combine those together and you get 4 * newCapacity.
    this.buffer = new Object[4 * newCapacity];
    this.numInserted = 0;
    if (prevBuffer != null) {
      for (int i = 0; i < prevBuffer.length; i += 2) {
        if (prevBuffer[i] != null) {
          putInternal(prevBuffer[i], prevBuffer[i + 1]);
        }
      }
    }
  }

  private void putInternal(Object k, Object v) {
    final int hash = System.identityHashCode(k);
    final int numEntries = buffer.length >>  1;
    //computing modulo with the assumption buffer.length is power of 2
    int index = hash & (numEntries-1);
    while (true) {
      if (buffer[2 * index] == null) {
        buffer[2 * index] = k;
        buffer[1 + (2 * index)] = v;
        numInserted++;
        return;
      }
      index = (index + 1) % numEntries;
    }
  }

  /**
   * Add a new (key, value) mapping.
   *
   * Inserting a new (key, value) never overwrites a previous one.
   * In other words, you can insert the same key multiple times and it will
   * lead to multiple entries.
   *
   * @param k Generics Type k.
   * @param v Generics Type v.
   */
  public void put(K k, V v) {
    Preconditions.checkNotNull(k);
    if (buffer == null) {
      realloc(DEFAULT_MAX_CAPACITY);
    } else if (numInserted + 1 > capacity) {
      realloc(capacity * 2);
    }
    putInternal(k, v);
  }

  private int getElementIndex(K k) {
    if (buffer == null) {
      return -1;
    }
    final int numEntries = buffer.length >> 1;
    final int hash = System.identityHashCode(k);
    //computing modulo with the assumption buffer.length is power of 2
    int index = hash & (numEntries -1);
    int firstIndex = index;
    do {
      if (buffer[2 * index] == k) {
        return index;
      }
      index = (index + 1) % numEntries;
    } while (index != firstIndex);
    return -1;
  }

  /**
   * Retrieve a value associated with a given key.
   *
   * @param k Generics Type k.
   * @return Generics Type V.
   */
  public V get(K k) {
    int index = getElementIndex(k);
    if (index < 0) {
      return null;
    }
    return (V)buffer[1 + (2 * index)];
  }

  /**
   * Retrieve a value associated with a given key, and delete the
   * relevant entry.
   *
   * @param k Generics Type k.
   * @return Generics Type V.
   */
  public V remove(K k) {
    int index = getElementIndex(k);
    if (index < 0) {
      return null;
    }
    V val = (V)buffer[1 + (2 * index)];
    buffer[2 * index] = null;
    buffer[1 + (2 * index)] = null;
    numInserted--;
    return val;
  }

  public boolean isEmpty() {
    return numInserted == 0;
  }

  public int numElements() {
    return numInserted;
  }

  public int capacity() {
    return capacity;
  }

  public interface Visitor<K, V> {
    void accept(K k, V v);
  }

  /**
   * Visit all key, value pairs in the IdentityHashStore.
   *
   * @param visitor visitor.
   */
  public void visitAll(Visitor<K, V> visitor) {
    int length = buffer == null ? 0 : buffer.length;
    for (int i = 0; i < length; i += 2) {
      if (buffer[i] != null) {
        visitor.accept((K)buffer[i], (V)buffer[i + 1]);
      }
    }
  }
}

相关信息

hadoop 源码目录

相关文章

hadoop ApplicationClassLoader 源码

hadoop AsyncDiskService 源码

hadoop AutoCloseableLock 源码

hadoop BasicDiskValidator 源码

hadoop BlockingThreadPoolExecutorService 源码

hadoop CacheableIPList 源码

hadoop ChunkedArrayList 源码

hadoop ClassUtil 源码

hadoop Classpath 源码

hadoop CleanerUtil 源码