散列表的相关内容

基于链表法解决哈希冲突的实现

该拉链发采用了一般性的策略，为M个元素分别构建符号表来保存散列值到这里的建。该代码是摘自算法（第四版）。

public class SequentialSearchST<Key, Value> {
    private Node first;//链表首结点
	private class Node{
		//链表结点的定义
		private final Key key;
		private Value val;
		private Node next;
		
		public Node(Key key, Value val, Node next) {
			this.key = key;
			this.val = val;
			this.next = next;
		}
		public Key getKey() {
			return key;
		}
 
		public Value getVal() {
			return val;
		}
 
		public void setVal(Value val) {
			this.val = val;
		}
 
		public Node getNext() {
			return next;
		}
 
		public void setNext(Node next) {
			this.next = next;
		}
		
	}
	//查找给定的键,返回相关联的值
	public Value get(Key key) {
		for(Node i = first; i != null; i = i.next) {
            if(key.equals(i.key))
            	return i.val;
		}
		return null;
	}
	//查找给定的键,找到则更新其值,否则在表中新建结点
	public void put(Key key, Value val) {
		for(Node i = first; i != null; i = i.next) {
			if(key.equals(i.key)) {
				i.val = val;
				return;
			}
		}
		first = new Node(key, val, first);
	}
	//删除结点
	public void delete(Key key) {
		first = delete(first, key);
	}
	private Node delete(Node x, Key key) {
		if(x == null) {
			return null;
		}
		if(key.equals(x.key)) {
			return x.next;
		}
		x.next = delete(x.next, key);
		return x;
	}
	public Iterable<Key> keys(){
		Queue<Key> q = new Queue<Key>();
		for(Node i = first;  i != null; i = i.next) {
			q.enqueue(i.key);
		}
		return q;
	}
	public Key getKey() {
		return first.key;
	}
}

public class SeparateChainingHashST<Key, Value> {
	//SequetialSearchST
	private int N;//键值对总数
	private int M;//散列表的大小
	private SequentialSearchST<Key, Value>[] st;//存放链表对象的数组
    public SeparateChainingHashST() {//默认的构造函数会使用997条链表
    	this(997);
    }
    public SeparateChainingHashST(int M) {
    	//创建M条链表
    	this.M = M;
    	//创造一个(SequentialSearchST<Key, Value>[])类型的,长度为M的数组
    	st = (SequentialSearchST<Key, Value>[]) new SequentialSearchST[M];
    	for(int i = 0; i < M; i++) {
    		//为每一个数组元素申请一个空间
    		st[i] = new SequentialSearchST();
    	}
    }
    private int hash(Key key) {
    	return (key.hashCode() & 0x7fffffff) % M;
    }
    public Value get(Key key) {
    	return (Value)st[hash(key)].get(key);
    }
    public void put(Key key, Value val) {
    	st[hash(key)].put(key, val);
    }
    public void delete(Key key) {
    	st[hash(key)].delete(key);
    }
    public Iterable<Key> keys(){
    	Queue<Key> queue = new Queue<Key>();
    	for(int i = 0; i < M; i++) {
    		System.out.println("第" + i +"个元素的链表");
    		for(Key key : st[i].keys()) {
    			queue.enqueue(key);
    			System.out.print(key + " " + get(key) + " ,");
    		}
    		System.out.println();
    	}
    	return queue;
    }
    public static void main(String[] args) {
    	SeparateChainingHashST<String, Integer> st = new SeparateChainingHashST<String, Integer>(5);
        for (int i = 0; i < 13; i++) {
            String key = StdIn.readString();
            st.put(key, i);
        }
        for (String s : st.keys())
            StdOut.println(s + " " + st.get(s));
        st.delete("M");
        StdOut.println("*************************************");
        for (String s : st.keys()) {
        	 StdOut.println(s + " " + st.get(s));
        }
    }
}

实现一个LRU缓存淘汰算法

采用一个链表来保存访问的数据，每次有新数据时看是否匹配已有的，有则将以保存的数据放到最前端，没有则将新数据保存至最前端。如果内存满了则从最末端删除数据。

public class LRULinkedHashMap<K, V> extends LinkedHashMap<K, V> {  
    private final int maxCapacity;  

    private static final float DEFAULT_LOAD_FACTOR = 0.75f;  

    private final Lock lock = new ReentrantLock();  

    public LRULinkedHashMap(int maxCapacity) {  
        super(maxCapacity, DEFAULT_LOAD_FACTOR, true);  
        this.maxCapacity = maxCapacity;  
    }  

    @Override 
    protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest) {  
        return size() > maxCapacity;  
    }  
    @Override 
    public boolean containsKey(Object key) {  
        try {  
            lock.lock();  
            return super.containsKey(key);  
        } finally {  
            lock.unlock();  
        }  
    }  


    @Override 
    public V get(Object key) {  
        try {  
            lock.lock();  
            return super.get(key);  
        } finally {  
            lock.unlock();  
        }  
    }  

    @Override 
    public V put(K key, V value) {  
        try {  
            lock.lock();  
            return super.put(key, value);  
        } finally {  
            lock.unlock();  
        }  
    }  

    public int size() {  
        try {  
            lock.lock();  
            return super.size();  
        } finally {  
            lock.unlock();  
        }  
    }  

    public void clear() {  
        try {  
            lock.lock();  
            super.clear();  
        } finally {  
            lock.unlock();  
        }  
    }  

    public Collection<Map.Entry<K, V>> getAll() {  
        try {  
            lock.lock();  
            return new ArrayList<Map.Entry<K, V>>(super.entrySet());  
        } finally {  
            lock.unlock();  
        }  
    }  
}