Skip to content

Latest commit

 

History

History
290 lines (239 loc) · 9.76 KB

WeakHashMap.md

File metadata and controls

290 lines (239 loc) · 9.76 KB

#WeakHashMap

前言:
WeakHashMap这个类我看了好久,一直不知道怎么写,有两点原因。第一:我怕把他写简单了,光从WeakHashMap的功能实现是描述,他和HashMap等非常的相似,无非也是用来hash表+单向链表的结构作为底层数据存储,再写一遍没太大意思。 第二:WeakHashMap的特点是以一种弱引用的关系存储数据,存储对象长期不用,可以被垃圾回收。讲这部分内容非常有意思,但是关于jvm部分了解不深,又怕讲不好。因此托了很长时间没写。
权衡以后,决定先讲解WeakHashMap弱引用的实现原理,垃圾回收部分先缓一缓。

#####一、与HashMap异同 WeakHashMap的实现和HashMap非常类似,他们有相同的数据结构,类似的存储机制。数据底层都是通过hash表+单向链表的结构存储数据。
1.get
获取元素的流程非常类似,首先对key进行hash处理,通过hash值寻找到对应的元素位置。数组元素保存的是单向链表,这是hash冲突导致的结果。然后元每个entry对比key值是否相同,最终找到对应的元素。

2.put
添加元素的流程也和HashMap类似,首先对key值hash处理,通过hash值求出对应的元素位置,然后通过对比单向链表中的key值,将元素添加到链表头部。最后会更加当前元素的数量与threshold对比,进行动态扩容。扩容部分的原理也和HashMap类似。

3.getTable
getTable方法是WeakHashMap特有的,这个方法是干什么用的呢?因为我们知道WeakHashMap的元素是通过弱引用的关系存储的。在容器中,有部分元素长时间未用,会被垃圾回收,getTable的作用就是清除被垃圾回收的元素。源码如下:

private Entry<K,V>[] getTable() {
    expungeStaleEntries();
    return table;
}
// 清除所有被垃圾回收的元素
private void expungeStaleEntries() {
	// queue队列中保存的是已经被垃圾回收的元素key值。遍历队列
    for (Object x; (x = queue.poll()) != null; ) {
        synchronized (queue) {
            @SuppressWarnings("unchecked")
                Entry<K,V> e = (Entry<K,V>) x;
            int i = indexFor(e.hash, table.length);

            Entry<K,V> prev = table[i];
            Entry<K,V> p = prev;
            while (p != null) {
                Entry<K,V> next = p.next;
                if (p == e) {
                    if (prev == e)
                        table[i] = next;
                    else
                        prev.next = next;
                    e.value = null; // 有助于垃圾回收
                    size--;
                    break;
                }
                prev = p;
                p = next;
            }
        }
    }
}

从源码中可以看出,首先会遍历queue队列,队列中保存的元素是已经被垃圾回收的元素的key值。然后将该key从table中删除。这步方法在getTable,resize,size方法中使用到,并且在垃圾回收过程中也会使用,因此他是在多线程环境下调用的,所以该方法使用了同步方法,确保线程安全。
那么是谁将垃圾回收的后的元素放入queue中的呢?这就要从Entry的结构说起。

4.Entry结构介绍
WeakHashMap的Entry是Reference的子类。Entry实例化时会引用当前的queue,如果当前Entry被垃圾回收后,会将key注册的queue中。在后文中我会详细介绍Reference类。

Entry结构

private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> {
    V value;
    final int hash;
    Entry<K,V> next;

    Entry(Object key, V value,
          ReferenceQueue<Object> queue,
          int hash, Entry<K,V> next) {
        super(key, queue);
        this.value = value;
        this.hash  = hash;
        this.next  = next;
    }

    ......
}
二、弱键引用

上文简单介绍了WeakHashMap和HashMap的异同点,大同小异,不想过多重复。我认为WeakHashMap的重点是对元素进行垃圾回收的部分。下面将结合源码进行讲解。

public abstract class Reference<T> {

 	private T referent;

	// 将回收的元素添加到队列中。
    volatile ReferenceQueue<? super T> queue;

    @SuppressWarnings("rawtypes")
    Reference next;

    transient private Reference<T> discovered;

    static private class Lock { };
    private static Lock lock = new Lock();

	// 垃圾收集器将回收的引用加入队列
    private static Reference<Object> pending = null;

    private static class ReferenceHandler extends Thread {

        ReferenceHandler(ThreadGroup g, String name) {
            super(g, name);
        }

        public void run() {
            for (;;) {
                Reference<Object> r;
                synchronized (lock) {
                    if (pending != null) {
                        r = pending;
                        pending = r.discovered;
                        r.discovered = null;
                    } else {
                        try {
                            try {
                                lock.wait();
                            } catch (OutOfMemoryError x) { }
                        } catch (InterruptedException x) { }
                        continue;
                    }
                }

                // Fast path for cleaners
                if (r instanceof Cleaner) {
                    ((Cleaner)r).clean();
                    continue;
                }

                ReferenceQueue<Object> q = r.queue;
                if (q != ReferenceQueue.NULL) q.enqueue(r);
            }
        }
    }

    static {
        ThreadGroup tg = Thread.currentThread().getThreadGroup();
        for (ThreadGroup tgn = tg;
             tgn != null;
             tg = tgn, tgn = tg.getParent());
        Thread handler = new ReferenceHandler(tg, "Reference Handler");
        handler.setPriority(Thread.MAX_PRIORITY);
        handler.setDaemon(true);
        handler.start();
    }

    。。。省略。。。
}

Reference的实现原理:

第一步通过静态代码块启动ReferenceHandler线程,所有Reference实例共享该线程。pending会被虚拟机调用,当有元素被垃圾回收以后,会添加到该队列中。Reference线程通过无线循环检查pending是否存在元素。当发现有元素被垃圾回收以后,会将该元素添加到queue中。如果当前没有发现被回收的元素,也就是pending为null时,会通过lock.wait() 阻塞线程。直到有元素被回收以后,会调用nodify唤醒线程。
该过程涉及到多线程的知识,jvm垃圾回收的原理等,这部分比较复杂,暂时无法很好的讲解。将回收的元素加入到queue队列的部分实现用了消费者模式。为了读者更好的理解该原理,我对他进行模仿,实现了一个简单的消费者模式的demo。这个demo主要功能如下:
1.多个生产者不断的生产某件产品,当产品数量大于10以后就停止生产,只要当产品数量小于10,就会生产。
2.多个消费者不断的消费产品,知道消费结束。
3.当生产者生产到10件以后,就阻塞生产线,通知消费者消费。
4.当消费者消费完结束以后,阻塞消费,通知生产者生产。

public class ProducerCustomerDemo {

	private static int index = 0;
	
	private static int size = 0;
	
	static private class Lock { };
    private static Lock lock = new Lock();
	
	private static Entry head = null;
	
	public synchronized int getSize() {
		return size;
	}

	public synchronized void addSize() {
		ProducerCustomerDemo.size++;
	}
	
	public synchronized void minusSize() {
		ProducerCustomerDemo.size--;
	}
	
	public synchronized int getIndex() {
		return index;
	}
	
	public synchronized void addIndex() {
		index++;
	}
	
	public synchronized void minusIndex() {
		index--;
	}
	
	public static void main(String[] args) {
		
		new Thread(new ProducerCustomerDemo().new Consumer("aaa")).start();
		new Thread(new ProducerCustomerDemo().new Consumer("bbb")).start();
		new Thread(new ProducerCustomerDemo().new Consumer("ccc")).start();
		new Thread(new ProducerCustomerDemo().new Consumer("ddd")).start();
		new Thread(new ProducerCustomerDemo().new Producer("张三")).start();
		new Thread(new ProducerCustomerDemo().new Producer("李四")).start();
	}
	
	class Entry {
		Entry next;
		int value;
		
		public Entry(int value) {
			this.value = value;
		}
	}
	
	class Consumer implements Runnable{

		private String name;
		
		public Consumer(String name) {
			this.name = name;
		}
		@Override
		public void run() {
			
			for (;;) {
				Entry temp = null;
				synchronized (lock) {
					if (head != null) {
						try {
							Thread.sleep(1000);
						} catch (InterruptedException e) {
							e.printStackTrace();
						}
						temp = head;
						head = temp.next;
						temp.next = null;
						minusSize();
						System.out.println("消费,当前产品数"+getSize()+"--"+name+":"+ temp.value);
						lock.notify();
					} else {
						try {
							lock.wait();
						} catch (InterruptedException e) {
							e.printStackTrace();
						}
					}
				}
			}
		}
		
	}
	
	class Producer implements Runnable {

		private String name;
		
		public Producer(String name) {
			this.name = name;
		}
		
		@Override
		public void run() {

			for (;;) {
				synchronized (lock) {
					if (getSize() < 10) {
						try {
							Thread.sleep(1000);
						} catch (InterruptedException e) {
							e.printStackTrace();
						}
						addIndex();
						Entry temp = new Entry(getIndex());
						temp.next = head;
						head = temp;
						addSize();
						System.out.println("生产,当前产品数"+getSize()+"--" + name + ":" + temp.value);
						lock.notify();
					} else {
						 try {
						 lock.wait();
						 } catch (InterruptedException e) {
						 e.printStackTrace();
						 }
					}
				}
			}
		}
	}
		
}