`
xiangkui
  • 浏览: 24979 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

磁盘HashMap实现(metaq 索引实现源码)

阅读更多

 

 

 

/*
 * (C) 2007-2012 Alibaba Group Holding Limited.
 * 
 * Licensed 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.
 * Authors:
 *   boyan <killme2008@gmail.com>
 */
package com.taobao.common.store.journal.impl;

import java.io.IOException;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

import com.taobao.common.store.journal.IndexMap;
import com.taobao.common.store.journal.OpItem;
import com.taobao.common.store.util.BytesKey;
import com.taobao.common.store.util.LRUHashMap;


/**
 * 
 * 基于LRU的IndexMap,可将LRU替换出来的OpItem存储于磁盘缓存
 * 
 * @author boyan
 * 
 * @since 1.0, 2009-10-20 上午11:04:37
 */

public class LRUIndexMap implements IndexMap {
    private final Lock lock = new ReentrantLock();
    private final LRUHashMap<BytesKey, OpItem> map;
    private final NotifyEldestEntryHandler handler;
    private final boolean enableLRU;


    public LRUIndexMap(final int capacity, final String cacheFilePath, final boolean enableLRU) throws IOException {
        this.enableLRU = enableLRU;
        map = new LRUHashMap<BytesKey, OpItem>(capacity, enableLRU);
        handler = new NotifyEldestEntryHandler(capacity, cacheFilePath);
        map.setHandler(handler);
    }


    @Override
    public void close() throws IOException {
        this.lock.lock();
        try {
            this.handler.close();
        }
        finally {
            this.lock.unlock();
        }
    }


    public LRUHashMap<BytesKey, OpItem> getMap() {
        return map;
    }


    public NotifyEldestEntryHandler getHandler() {
        return handler;
    }


    @Override
    public boolean containsKey(final BytesKey key) {
        this.lock.lock();
        try {

            return map.containsKey(key) || (enableLRU && this.handler.getDiskMap().get(key) != null);
        }
        catch (final IOException e) {
            throw new IllegalStateException("查询Key失败", e);
        }
        finally {
            this.lock.unlock();
        }
    }


    @Override
    public OpItem get(final BytesKey key) {
        this.lock.lock();
        try {
            OpItem result = map.get(key);
            if (result == null && enableLRU) {
                result = handler.getDiskMap().get(key);
            }
            return result;
        }
        catch (final IOException e) {
            throw new IllegalStateException("访问磁盘缓存失败", e);
        }
        finally {
            this.lock.unlock();
        }

    }

    class LRUIndexMapItreator implements Iterator<BytesKey> {

        private final Iterator<BytesKey> mapIt;
        private final Iterator<BytesKey> diskMapIt;
        private volatile boolean enterDisk;
        private BytesKey currentKey;


        public LRUIndexMapItreator(final Iterator<BytesKey> mapIt, final Iterator<BytesKey> diskMapIt) {
            super();
            this.mapIt = mapIt;
            this.diskMapIt = diskMapIt;
        }


        @Override
        public boolean hasNext() {
            lock.lock();
            try {
                if (mapIt.hasNext()) {
                    return true;
                }
                if (enableLRU) {
                    if (!enterDisk) {
                        enterDisk = true;
                    }
                    return diskMapIt.hasNext();
                }
                return false;
            }
            finally {
                lock.unlock();
            }
        }


        @Override
        public BytesKey next() {
            lock.lock();
            try {
                BytesKey result = null;
                if (!enterDisk) {
                    result = mapIt.next();
                }
                else {
                    result = diskMapIt.next();
                }
                this.currentKey = result;
                return result;
            }
            finally {
                lock.unlock();
            }
        }


        @Override
        public void remove() {
            lock.lock();
            try {
                if (currentKey == null) {
                    throw new IllegalStateException("The next method is not been called");
                }
                LRUIndexMap.this.remove(this.currentKey);
            }
            finally {
                lock.unlock();
            }
        }

    }


    @Override
    public Iterator<BytesKey> keyIterator() {
        lock.lock();
        try {
            return new LRUIndexMapItreator(new HashSet<BytesKey>(map.keySet()).iterator(), handler.getDiskMap()
                .iterator());
        }
        finally {
            lock.unlock();
        }
    }


    @Override
    public void put(final BytesKey key, final OpItem opItem) {
        lock.lock();
        try {
            this.map.put(key, opItem);
        }
        finally {
            lock.unlock();
        }
    }


    @Override
    public void putAll(final Map<BytesKey, OpItem> map) {
        lock.lock();
        try {
            this.map.putAll(map);
        }
        finally {
            lock.unlock();
        }
    }


    @Override
    public void remove(final BytesKey key) {
        lock.lock();
        try {
            final OpItem result = map.remove(key);
            if (result == null && enableLRU) {
                try {
                    handler.getDiskMap().remove(key);
                }
                catch (final IOException e) {
                    throw new IllegalStateException("访问磁盘缓存失败", e);
                }
            }
        }
        finally {
            lock.unlock();
        }
    }


    @Override
    public int size() {
        lock.lock();
        try {
            return map.size() + handler.getDiskMap().size();
        }
        finally {
            lock.unlock();
        }
    }

}

 

/*
 * (C) 2007-2012 Alibaba Group Holding Limited.
 * 
 * Licensed 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.
 * Authors:
 *   boyan <killme2008@gmail.com>
 */
package com.taobao.common.store.journal.impl;

import java.io.File;
import java.io.IOException;
import java.io.RandomAccessFile;
import java.nio.MappedByteBuffer;
import java.nio.channels.FileChannel;
import java.nio.channels.FileChannel.MapMode;
import java.util.Arrays;
import java.util.BitSet;
import java.util.Iterator;

import com.taobao.common.store.journal.OpItem;
import com.taobao.common.store.util.BytesKey;


/**
 * 
 * 基于开放地址法,存储于硬盘上的HashMap
 * 
 * @author boyan
 * 
 * @since 1.0, 2009-10-20 上午11:27:07
 */

public class OpItemHashMap {
    private final OpItemEntry[] table;

    public static final int DEFAULT_CAPACITY = 256;

    private final BitSet bitSet;

    private final File file;

    private final FileChannel channel;

    private final MappedByteBuffer mappedByteBuffer;


    public OpItemHashMap(final int capacity, final String cacheFilePath, final boolean force) throws IOException {
        if (capacity <= 0) {
            throw new IllegalArgumentException("capacity<=0");
        }
        this.file = new File(cacheFilePath);
        this.file.createNewFile();
        this.bitSet = new BitSet(OpItemEntry.SIZE * capacity);
        this.channel = new RandomAccessFile(file, force ? "rws" : "rw").getChannel();
        this.mappedByteBuffer =
                this.channel.map(MapMode.READ_WRITE, OpItemEntry.SIZE * capacity / 2, OpItemEntry.SIZE * capacity);
        this.table = new OpItemEntry[capacity];
    }


    private int hash(final int keyHash, final int i) {
        return this.abs(this.hash1(keyHash) + i * this.hash2(keyHash)) % table.length; // 双重散列
    }


    private int hash1(final int keyHash) {
        return keyHash % table.length;
    }


    private int hashForKey(final BytesKey k) {
        final int hash = k.hashCode();
        return this.abs(hash);
    }


    private int abs(int hash) {
        if (hash == Integer.MIN_VALUE) {
            hash = 0;
        }
        return Math.abs(hash);
    }


    private int hash2(final int keyHash) {
        return keyHash % (table.length - 2);
    }


    public boolean put(final BytesKey key, final OpItem value) throws IOException {
        if (this.loadFactor() > 0.75f) {
            return false;
        }
        final int keyHash = this.hashForKey(key);
        int j = this.hash1(keyHash);
        int offset = this.calcOffset(j);
        int i = 0;
        final int m = table.length;
        // 定位
        while (this.table[j] != null && !this.isEntryDeleted(j) && this.bitSet.get(offset) && i < m) {
            j = this.hash(keyHash, i++);
            offset = this.calcOffset(j);
        }
        if (table[j] == null || table[j].isDeleted()) {
            table[j] = new OpItemEntry(value, false);
            final byte[] buffer = table[j].encode();
            if (buffer != null) {
                this.mappedByteBuffer.position(offset);
                this.mappedByteBuffer.put(buffer, 0, buffer.length);
                bitSet.set(offset, true);
            }
            // 从内存释放
            table[j].unload();
            return true;
        }
        else {
            return false;
        }

    }


    private int calcOffset(final int j) {
        return j * OpItemEntry.SIZE;
    }


    private boolean isEntryDeleted(final int j) throws IOException {
        if (!this.table[j].isLoaded()) {
            this.table[j].load(mappedByteBuffer, this.calcOffset(j), false);
        }
        this.table[j].unload(); // 记得释放
        return this.table[j].isDeleted();
    }


    public OpItem get(final BytesKey key) throws IOException {
        final int keyHash = this.hashForKey(key);
        int j = this.hash1(keyHash);
        int i = 0;
        final int m = table.length;
        while (this.table[j] != null && i < m) {
            if (!table[j].isLoaded()) {
                table[j].load(this.mappedByteBuffer, this.calcOffset(j), true);
            }
            if (table[j].getOpItem() != null && Arrays.equals(table[j].getOpItem().getKey(), key.getData())) {
                if (table[j].isDeleted()) {
                    return null;
                }
                else {
                    return table[j].getOpItem();
                }
            }
            else {
                table[j].unload();// 记住清除
            }
            j = this.hash(keyHash, i++);
        }
        return null;
    }


    public OpItem remove(final BytesKey key) throws IOException {

        final int keyHash = this.hashForKey(key);
        int j = this.hash1(keyHash);
        int i = 0;
        final int m = table.length;
        while (this.table[j] != null && i < m) {
            final int offset = this.calcOffset(j);
            if (!table[j].isLoaded()) {
                table[j].load(mappedByteBuffer, offset, true);
            }
            if (table[j].getOpItem() != null && Arrays.equals(table[j].getOpItem().getKey(), key.getData())) {
                if (table[j].isDeleted()) {
                    return null;
                }
                else {
                    table[j].setDeleted(true);
                    this.bitSet.set(offset, false);
                    // 写入磁盘
                    this.mappedByteBuffer.put(offset, DELETED);
                    return table[j].getOpItem();
                }
            }
            else {
                table[j].unload();// 切记unload
            }
            j = this.hash(keyHash, i++);
        }
        return null;

    }


    public void close() throws IOException {
        if (this.channel != null) {
            this.channel.close();
            file.delete();
        }
    }

    class DiskIterator implements java.util.Iterator<BytesKey> {
        private int currentIndex = 0;
        private int lastRet = -1;


        @Override
        public boolean hasNext() {

            int i = this.currentIndex;
            if (i >= table.length) {
                return false;
            }
            while (!this.isExists(i)) {
                if (i == table.length - 1) {
                    return false;
                }
                i++;
            }
            return true;

        }


        private boolean isExists(final int i) {
            return table[i] != null && !table[i].isDeleted();
        }


        @Override
        public BytesKey next() {
            try {
                if (currentIndex >= table.length) {
                    return null;
                }
                while (!this.isExists(currentIndex)) {
                    if (currentIndex == table.length - 1) {
                        return null;
                    }
                    currentIndex++;
                }
                if (!table[currentIndex].isLoaded()) {
                    table[currentIndex].load(mappedByteBuffer, OpItemHashMap.this.calcOffset(currentIndex), true);
                }
                final BytesKey key = new BytesKey(table[currentIndex].getOpItem().getKey());
                this.currentIndex++;
                this.lastRet++;
                return key;
            }
            catch (final IOException e) {
                throw new IllegalStateException("Load OpItem fail", e);
            }

        }


        @Override
        public void remove() {
            if (this.lastRet == -1) {
                throw new IllegalStateException("The next method is not been called");
            }
            table[currentIndex - 1].setDeleted(true);
            bitSet.set(OpItemHashMap.this.calcOffset(currentIndex - 1), false);
            // 写入磁盘
            mappedByteBuffer.put(OpItemHashMap.this.calcOffset(currentIndex - 1), DELETED);
            lastRet = -1;
        }

    }


    public Iterator<BytesKey> iterator() {
        return new DiskIterator();
    }

    static final byte DELETED = (byte) 1;


    public int size() {
        return this.bitSet.cardinality();
    }


    private float loadFactor() {
        return (float) this.bitSet.cardinality() / this.table.length;
    }

}

 

 

fas

分享到:
评论

相关推荐

    hashmap实现原理

    HashMap的实现基于哈希表的概念,它通过计算对象的哈希码来快速定位数据,从而实现了O(1)的平均时间复杂度。在深入探讨HashMap的实现原理之前,我们需要了解两个关键的接口方法:`hashCode()`和`equals()`。 根据...

    Java中用hashmap实现购物车

    Java语言使用hashmap实现向购物车添加删除修改商品,显示商品信息

    HashMap源码分析

    HashMap 是 Java 中最常用的集合类之一,它是基于哈希表实现的,提供了高效的数据存取功能。HashMap 的核心原理是将键(key)通过哈希函数转化为数组索引,然后将键值对(key-value pair)存储在数组的对应位置。...

    HashMap源码深度剖析.md

    HashMap源码深度剖析,面试必备

    java学习笔记,包括JVM,并发,JDK一些工具的源码,spring,hashMap实现源码分析

    java学习笔记,包括JVM,并发,JDK一些工具的源码,spring,hashMap实现源码分析

    HashMap之resize()方法源码解读.docx

    HashMap之resize()方法源码解读 HashMap的resize()方法是HashMap中最核心的方法之一,该方法负责扩容HashMap的容量,以便存储更多的键值对。下面我们将对HashMap的resize()方法进行源码解读,了解其扩容机制和原理...

    HashMap源码实现红黑树添加元素和删除元素

    HashMap 源码实现红黑树添加元素和删除元素 HashMap 中使用红黑树来存储元素,是为了提高查找、插入和删除操作的性能。红黑树是一种自平衡二叉树,可以保持二叉树的平衡,从而获得较高的查找性能。 红黑树的创建...

    HashMap源码(JDK1.7,含注释)

    HashMap源码(JDK1.7,含注释)

    基于JavaScript的HashMap实现

    在JavaScript中,HashMap是一种常用的键值对存储结构,它提供了快速的插入、删除和查找操作。...通过阅读和理解HashMap.js文件中的源码,开发者可以更好地掌握JavaScript的底层原理,并在实际项目中灵活应用。

    HashMap源码(上)

    HashMap的部分源码解析

    面试必考之HashMap源码分析与实现

    面试中,HashMap的源码分析与实现是一个常见的考察点,因为它涉及到数据结构、并发处理和性能优化等多个核心领域。本篇文章将深入探讨HashMap的内部工作原理、关键特性以及其在实际应用中的考量因素。 HashMap基于...

    hashMap1.8源码

    下面我们将深入探讨HashMap的源码,特别是关于`put`和`get`操作的实现细节。 HashMap的核心数据结构是一个数组配合链表/红黑树的数据结构。数组中的每个元素是一个Node对象,Node包含键、值、哈希码以及指向下一个...

    如何得到hashmap的索引

    ### 如何得到HashMap的索引 在Java编程中,`HashMap`是一种常见的数据结构,它提供了基于键值对(Key-Value Pair)的数据存储方式。然而,“索引”这一概念通常与数组或列表关联,而在`HashMap`中,我们通过键(Key...

    hashmap的C++实现

    hashmap的C++实现,对于学习C++方面的很有用

    电话本管理系统HashMap实现

    在这个系统中,使用HashMap实现是一种高效且灵活的方法,因为HashMap提供了快速的查找和插入操作。本文将深入探讨如何使用HashMap来构建一个电话本管理系统,并通过源码分析增强理解。 HashMap是Java集合框架中的一...

    易语言源码易语言HashMap类源码.rar

    在给定的压缩包“易语言源码易语言HashMap类源码.rar”中,包含了易语言实现的HashMap类的源代码。HashMap是一种常见的数据结构,在许多编程语言中都有实现,它提供了快速的键值对存储和查找功能。 HashMap类是基于...

    1.6 hashmap源码

    hashmap源码,可以看看http://blog.csdn.net/wabiaozia/article/details/50684556

    用hashmap实现词典查询

    本话题主要关注如何利用HashMap这一数据结构来实现词典查询,以提供快速、便捷的字典服务。HashMap是Java编程语言中的一种内置数据结构,它提供了O(1)的平均时间复杂度来执行查找、插入和删除操作,这使得它成为构建...

    Hashmap实现了Map接口的底层实现.docx

    HashMap是Java编程语言中一种非常重要的数据结构,它实现了Map接口,允许存储键值对,且支持null键和null值。HashMap的底层实现基于数组和链表,这使得它具有较快的查找速度。以下是关于HashMap的详细说明: 一、...

Global site tag (gtag.js) - Google Analytics