Fast Read Map
One. introduction
In the process of work, we often encounter the following needs:
With a MAP stored Object, the frequency of the MAP is very high, and the frequency of writing is very low (generally only written when it is initialized, or reloaded). Although the conflict of reading and writing is rare, but once, the internal structure of the MAP may be chaotic, so we have to add a synchronous lock for MAP.
This article introduces an indirect "fast reading map" to achieve ideas and code, which can avoid reading and writing conflicts, but also achieve the highest read speed.
The formation of the final code of the "Quick Read Map" depends on the discussion and improvement of netizens Octfor. See the entire discussion process
http://forum.javaeye.com/viewtopic.php?t=11315
The history background of "Fast Read Map" is described in detail below, forming ideas, code implementation.
Securrent Map
The simplest implementation of Concurrent Map is to use the java.util.hashtable class, or modify a map with collections.synchronizedmap ().
The MAP thus obtained ensures read and write synchronization, but when and occurs, it must be synchronized, serial read, and the efficiency is very low. This idea is obviously not suitable.
Doug LEA provides a Concurrent kit,
Http://gee.cs.oswego.edu/dl/classes/edu/oswego/cs/dl/util/concurrent/intro.html
Includes Lock, Readwritelock, Currenthashmap, CurrentReaderHashmap, etc. JDK1.5 introduces these classes as java.util.concurrent packages.
I envisioned, currenthashmap should be read and write synchronization using REDWRITELOCK. The code should look like this.
[code]
// my guess class CocurrentHashMap {Private Map map = null; final ReadWriteLock rwLock = new ...;. Final Lock readLock = rwLock.readLock (); final Lock writeLock = rwLock.writeLock (); // decorate the map as concurrent public CocurrentHashMap (MAP M) {MAP = M;} // All Write Method, Like Put, Putall, Remove, Clear Public Void Putall (MAP M) {WriteLock.lock (); Try {Map.Putall (M);} finally { Writelock.unlock ();}} // all read method. like Get, ContainSkey, ContaSValue, entryset () public object get (object key) {readlock.lock (); try {return map.get (key);} finally {Readlock.unlock ();}}; // AS we can see, in such places it is communication to use aop here. :-)
[/ code]
But I saw the code of currenthashmap and found not this. The implementation is more complicated, and the TABLE is separately managed. The internal class Segment Extends ReentrantLock. The restvalueunderlock method inside is Lock. [code]
/ ** * Read value field of an entry under lock. Called if value * field ever appears to be null. This is possible only if a * compiler happens to reorder a HashEntry initialization with * its table assignment, which is legal under memory model * But is not known to EVER OCCUR. * / V ReadValueUnderlock (HashenTry
[/ code]
Let's take a look at CurrentReaderhashmap, "a Version of Hashtable That Supports Mostly-Concurrent Reading, But Exclusive Writing."
Http://gee.cs.oswego.edu/dl/classes/edu/oswego/cs/dl/util/concurrent/concurrentreaderhashmap.java
However, its read (get, contains, size ...) method is used in Synchronized. Still get the system lock.
Third, read MAP
Read Lock is also LOCK, and there is Overhead. Can you find a method to ensure that it is not a lock, while writing, can you guarantee the correct data structure and content?
Basic ideas is to let read and write operations on different maps, and then synchronize two MAP after each write. code show as below:
[code]
/ *
* Read Write Map
*
* Write is expensive.
* Read is Fast As Pure Hashmap.
*
* NOTE: Extra Info is Removed for Free Uses
* /
Package Net.UTIL;
Import java.lang.compiler;
Import java.util.collection;
Import java.util.map;
Import java.util.set;
Import java.util.hashmap;
Import java.util.collections;
Public Class READWRITEMAP IMPLEMENTS MAP {
Protected volatile maptoread = getnewmap ();
// you can override it as new treem ();
protected map getnewmap () {
Return new hashmap ();
}
// Copy Maptowrite to Maptoread
protected map copy () {
Map newmap = getnewmap ();
NewMap.putall (Maptoread);
Return newMap;
}
// read methods
Public int size () {return maptoread.size ();
}
Public Boolean ISempty () {
Return maptoread.isempty ();
}
Public Boolean ContainsKey (Object Key) {
Return maptoread.containskey (key);
}
Public Boolean ContaSvalue (Object Value) {
Return maptoread.containsvalue (value);
}
Public collection value () {
Return maptoread.values ();
}
Public set entryset () {
Return maptoread.entryset ();
}
PUBLIC SET KeySet () {
Return maptoread.keyset ();
}
Public Object Get (Object Key) {
Return maptoread.get (key);
}
// Write Methods
Public synchronized void clear () {
Maptoread = getNewMap ();
}
Public synchronized object remove (Object key) {
Map Map = Copy ();
Object o = map.remove (key);
Maptoread = Map;
Return O;
}
Public Synchronized Object Put (Object Key, Object Value) {
Map Map = Copy ();
Object o = map.put (key, value);
Maptoread = Map;
Return O;
}
Public Synchronized Void Putall (Map T) {
Map Map = Copy ();
Map.putall (t);
Maptoread = Map;
}
}
[/ code]
When this MAP is read, it is as fast as ordinary Hashmap.
When writing, first copy the internal map, then modify it on this backup, after the change, let the internal MAP are equal to this modified MAP. This method is synchronously protected to avoid simultaneous write operations. It can be seen that when writing, the overhead is quite large. Try to use Putall () Method.
