Thinking
HashMap 和HashSet其实类似于具有特定存储方式的二维数组。拿Integerhashset为例，我想要往hashset里面存储一个数字5，首先先通过某一种hash算法获得一个hash值比如获得的是3，那么先纵向遍历，查看二维数组的纵列第三个位置上是否为空，如果为空，就将该二维数组的横向初始化，然后把数字5放进初始化的横向数组里面；如果，二维数组第三个位置不为空，那么再继续横向遍历找到位置三并将数字5放入（注意：如果该位置也有值那么会覆盖掉原来的值）
plsql IntegerSet
CREATE OR REPLACE TYPE IntegerSet_gdb AS OBJECT (chains IntegerarrayArray , numChains integer , numEntries integer , threshold integer , --阈值
loadFactor float ,
cachedChain integer , cachedChainPos integer , CONSTRUCTOR FUNCTION IntegerSet_gdb RETURN SELF AS RESULT, MEMBER PROCEDURE put (k INTEGER ), MEMBER FUNCTION get (k INTEGER ) RETURN boolean , MEMBER FUNCTION getByIndex (self IN OUT NOCOPY IntegerSet_gdb , idx integer ) RETURN INTEGER , MEMBER PROCEDURE remove (k INTEGER ), MEMBER PROCEDURE clear, MEMBER FUNCTION getNumEntries RETURN integer , --整个set里面存储内容的个数 MEMBER FUNCTION isEmpty RETURN boolean , MEMBER FUNCTION toString RETURN varchar2 , MEMBER FUNCTION toArray RETURN IntegerArray_1 , MEMBER FUNCTION getKeyPosition (key INTEGER ) RETURN integer ) ; --通过Hash算法获取hash值 / CREATE OR REPLACE TYPE BODY IntegerSet_gdb AS CONSTRUCTOR FUNCTION IntegerSet_gdb RETURN SELF AS RESULT AS i integer ; BEGIN self.numChains := 11; self.numEntries := 0; self.loadFactor := 0.75; self.threshold := floor (self.numChains * self.loadFactor ); self.cachedChain := 0; self.cachedChainPos := 0; self.chains := IntegerarrayArray (); self.chains.extend (self.numChains ); RETURN; END; MEMBER PROCEDURE put (k INTEGER ) AS pos integer ; newChains IntegerarrayArray ; BEGIN IF self.numEntries > self.threshold THEN --对超出阈值进行处理 self.numChains := self.numChains * 2; self.threshold := floor (self.numChains * self.loadFactor ); newChains := IntegerarrayArray (); newChains.extend (self.numChains ); FOR i IN 1..self.chains.count LOOP IF self.chains (i ) IS NOT NULL THEN FOR j IN 1..self.chains (i ).count LOOP IF self.chains (i )(j ) IS NOT NULL THEN pos := getKeyPosition (self.chains (i )(j )); IF newChains (pos ) IS NULL THEN newChains (pos ) := IntegerArray_1 (); END IF; newChains (pos ).extend; newChains (pos )(newChains (pos ).count) := self. chains (i )(j ); END IF; END LOOP; END IF; END LOOP; self.chains := newChains ; self.put (k ); END IF; pos := getKeyPosition (k ); --获取hash值 IF self.chains (pos ) IS NOT NULL THEN FOR i IN 1..self.chains (pos ).count LOOP IF self.chains (pos )(i ) = k THEN RETURN; END IF; END LOOP; FOR i IN 1..self.chains (pos ).count LOOP IF self.chains (pos )(i ) IS NULL THEN self.chains (pos )(i ) := k ; self.numEntries := self.numEntries + 1; --总个数+1 RETURN; END IF; END LOOP; self.chains (pos ).extend; self.chains (pos )(self.chains (pos ).count) := k ; --放入value self.numEntries := self.numEntries + 1; ELSE self.chains (pos ) := IntegerArray_1 (); self.put (k ); END IF; END; MEMBER FUNCTION get (k INTEGER ) RETURN boolean AS pos integer ; i integer ; BEGIN pos := getKeyPosition (k ); IF self.chains (pos ) IS NOT NULL THEN FOR i IN 1..self.chains (pos ).count LOOP IF self.chains (pos )(i ) = k THEN RETURN TRUE; END IF; END LOOP; END IF; RETURN FALSE; END; MEMBER PROCEDURE clear AS oldNumChains integer ; BEGIN self.numEntries := 0; oldNumChains := self.numChains ; self.numChains := 11; self.chains.trim (self.numChains - oldNumChains ); self.threshold := floor (self.numChains * self.loadFactor ); FOR i IN 1..self.chains.count LOOP IF ( self.chains (i ) IS NOT NULL) THEN self.chains (i ).delete; END IF; END LOOP; END; MEMBER PROCEDURE remove (k INTEGER ) AS pos integer ; i integer ; BEGIN pos := getKeyPosition (k ); IF self.chains (pos ).count IS NOT NULL THEN FOR i IN 1..self.chains (pos ).count LOOP IF self.chains (pos )(i ) = k THEN self.chains (pos )(i ) := NULL; self.numEntries := self.numEntries - 1; END IF; END LOOP; END IF; END; MEMBER FUNCTION getNumEntries RETURN integer AS BEGIN RETURN self.numEntries ; END; MEMBER FUNCTION isEmpty RETURN boolean AS BEGIN IF self.getNumEntries () = 0 THEN RETURN TRUE; ELSE RETURN FALSE; END IF; END; MEMBER FUNCTION getByIndex (self IN OUT IntegerSet_gdb , idx integer ) RETURN INTEGER AS BEGIN IF idx >= 1 AND idx <= self.getNumEntries THEN IF self.cachedChain = 0 OR idx = 1 THEN self.cachedChain := 1; self.cachedChainPos := 0; END IF; FOR i IN self.cachedChain ..self.chains.count LOOP IF self.chains (i ) IS NOT NULL THEN FOR j IN self.cachedChainPos + 1..self.chains (i ).count LOOP IF self.chains (i )(j ) IS NOT NULL THEN self.cachedChainPos := j ; RETURN self.chains (i )(j ); END IF; END LOOP; END IF; self.cachedChainPos := 0; self.cachedChain := self.cachedChain + 1; END LOOP; END IF; END; MEMBER FUNCTION toString RETURN varchar2 AS res VARCHAR2 (32767); BEGIN res := ''; FOR i IN 1..self.chains.count LOOP IF self.chains (i ) IS NOT NULL THEN FOR j IN 1..self.chains (i ).count LOOP IF self.chains (i )(j ) IS NOT NULL THEN res := res || ', ' || TO_CHAR (self.chains (i )(j )); END IF; END LOOP; END IF; END LOOP; res := '{ ' || substr (res , 3) || ' }'; RETURN res ; END; MEMBER FUNCTION toArray RETURN IntegerArray_1 AS res IntegerArray_1 ; BEGIN res := IntegerArray_1 (); FOR i IN 1..self.chains.count LOOP IF self.chains (i ) IS NOT NULL THEN FOR j IN 1..self.chains (i ).count LOOP IF self.chains (i )(j ) IS NOT NULL THEN res.extend ; res (res.count ) := self.chains (i )(j ); END IF; END LOOP; END IF; END LOOP; RETURN res ; END; MEMBER FUNCTION getKeyPosition (key INTEGER ) RETURN integer IS BEGIN RETURN mod (abs (integerIdentity (key )), self.numChains ) + 1; END; END ; /
plsql varchar2varchar2Map
CREATE OR REPLACE TYPE Varchar2Varchar2Map_gdb AS OBJECT (chains Vrchr2vrchr2mp1ntryrryArr , numChains integer , numEntries integer , threshold integer , loadFactor float , CONSTRUCTOR FUNCTION Varchar2Varchar2Map_gdb RETURN SELF AS RESULT, MEMBER PROCEDURE put (k VARCHAR2 , v VARCHAR2 ), MEMBER FUNCTION get (k VARCHAR2 ) RETURN VARCHAR2 , MEMBER PROCEDURE remove (k VARCHAR2 ), MEMBER FUNCTION containsKey (k VARCHAR2 ) RETURN boolean , MEMBER FUNCTION getKeys RETURN Varchar2Set_gdb , MEMBER FUNCTION getEntries RETURN Varchar2varchar2map1entrySet , MEMBER FUNCTION getNumEntries RETURN integer , MEMBER FUNCTION isEmpty RETURN boolean , MEMBER PROCEDURE clear, MEMBER FUNCTION toString RETURN varchar2 , MEMBER FUNCTION getKeyPosition (key VARCHAR2 ) RETURN integer ) ; / CREATE OR REPLACE TYPE BODY Varchar2Varchar2Map_gdb AS CONSTRUCTOR FUNCTION Varchar2Varchar2Map_gdb RETURN SELF AS RESULT AS i integer ; BEGIN self.numChains := 11; self.numEntries := 0; self.loadFactor := 0.75; self.threshold := floor (self.numChains * self.loadFactor ); self.chains := Vrchr2vrchr2mp1ntryrryArr (); self.chains.extend (self.numChains ); RETURN; END; MEMBER PROCEDURE put (k VARCHAR2 , v VARCHAR2 ) AS pos integer ; newChains Vrchr2vrchr2mp1ntryrryArr ; BEGIN IF self.numEntries > self.threshold THEN self.numChains := self.numChains * 2; self.threshold := floor (self.numChains * self.loadFactor ); newChains := Vrchr2vrchr2mp1ntryrryArr (); newChains.extend (self.numChains ); FOR i IN 1..self.chains.count LOOP IF self.chains (i ) IS NOT NULL THEN FOR j IN 1..self.chains (i ).count LOOP IF self.chains (i )(j ) IS NOT NULL THEN pos := getKeyPosition (self.chains (i )(j ).k); IF newChains (pos ) IS NULL THEN newChains (pos ) := Varchar2varchar2map1entryArray (); END IF; newChains (pos ).extend; newChains (pos )(newChains (pos ).count) := self. chains (i )(j ); END IF; END LOOP; END IF; END LOOP; self.chains := newChains ; self.put (k , v ); END IF; pos := getKeyPosition (k ); IF self.chains (pos ) IS NOT NULL THEN FOR i IN 1..self.chains (pos ).count LOOP IF self.chains (pos )(i ).k = k THEN self.chains (pos )(i ).v := v ; RETURN; END IF; END LOOP; FOR i IN 1..self.chains (pos ).count LOOP IF self.chains (pos )(i ) IS NULL THEN self.chains (pos )(i ) := Varchar2Varchar2Map1Entry_gdb (k , v ); self.numEntries := self.numEntries + 1; RETURN; END IF; END LOOP; self.chains (pos ).extend; self. chains (pos )(self. chains (pos ).count) := Varchar2Varchar2Map1Entry_gdb (k , v ); self.numEntries := self.numEntries + 1; ELSE self.chains (pos ) := Varchar2varchar2map1entryArray (); self.put (k , v ); END IF; END; MEMBER FUNCTION get (k VARCHAR2 ) RETURN VARCHAR2 AS pos integer ; i integer ; BEGIN pos := getKeyPosition (k ); IF self.chains (pos ) IS NOT NULL THEN FOR i IN 1..self.chains (pos ).count LOOP IF self.chains (pos )(i ).k = k THEN RETURN self.chains (pos )(i ).v; END IF; END LOOP; END IF; RETURN NULL; END; MEMBER PROCEDURE remove (k VARCHAR2 ) AS pos integer ; i integer ; BEGIN pos := getKeyPosition (k ); IF self.chains (pos ) IS NOT NULL THEN FOR i IN 1..self.chains (pos ).count LOOP IF self.chains (pos )(i ).k = k THEN self.chains (pos )(i ) := NULL; self.numEntries := self.numEntries - 1; END IF; END LOOP; END IF; END; MEMBER FUNCTION getKeys RETURN Varchar2Set_gdb AS keys Varchar2Set_gdb ; BEGIN keys := Varchar2Set_gdb (); FOR i IN 1..self.chains.count LOOP IF self.chains (i ) IS NOT NULL THEN FOR j IN 1..self.chains (i ).count LOOP IF self.chains (i )(j ) IS NOT NULL THEN keys.put (self.chains (i )(j ).k); END IF; END LOOP; END IF; END LOOP; RETURN keys ; END; MEMBER FUNCTION getEntries RETURN Varchar2varchar2map1entrySet AS entries Varchar2varchar2map1entrySet ; BEGIN entries := Varchar2varchar2map1entrySet (); FOR i IN 1..self.chains.count LOOP IF self.chains (i ) IS NOT NULL THEN FOR j IN 1..self.chains (i ).count LOOP IF self.chains (i )(j ) IS NOT NULL THEN entries. put (Varchar2Varchar2Map1Entry_gdb (self.chains (i )(j ).k, self. chains (i )(j ).v)); END IF; END LOOP; END IF; END LOOP; RETURN entries ; END; MEMBER FUNCTION containsKey (k VARCHAR2 ) RETURN boolean AS pos integer ; i integer ; BEGIN pos := getKeyPosition (k ); IF self.chains (pos ) IS NOT NULL THEN FOR i IN 1..self.chains (pos ).count LOOP IF self.chains (pos )(i ).k = k THEN RETURN TRUE; END IF; END LOOP; END IF; RETURN FALSE; END; MEMBER FUNCTION getNumEntries RETURN integer AS BEGIN RETURN self.numEntries ; END; MEMBER FUNCTION isEmpty RETURN boolean AS BEGIN IF self.getNumEntries () = 0 THEN RETURN TRUE; ELSE RETURN FALSE; END IF; END; MEMBER PROCEDURE clear AS oldNumChains integer ; BEGIN self.numEntries := 0; oldNumChains := self.numChains ; self.numChains := 11; self.chains.trim (self.numChains - oldNumChains ); self.threshold := floor (self.numChains * self.loadFactor ); FOR i IN 1..self.chains.count LOOP IF ( self.chains (i ) IS NOT NULL) THEN self.chains (i ).delete; END IF; END LOOP; END; MEMBER FUNCTION toString RETURN varchar2 AS res VARCHAR2 (32767); BEGIN res := ''; FOR i IN 1..self.chains.count LOOP IF self.chains (i ) IS NOT NULL THEN FOR j IN 1..self.chains (i ).count LOOP IF self.chains (i )(j ) IS NOT NULL THEN res := res || ', ' || self.chains (i )(j ).toString(); END IF; END LOOP; END IF; END LOOP; res := '{ ' || substr (res , 3) || ' }'; RETURN res ; END; MEMBER FUNCTION getKeyPosition (key VARCHAR2 ) RETURN integer IS BEGIN RETURN mod (abs (djb2 (key )), self.numChains ) + 1; END; END ; /
refference
http://blog.csdn.net/vking_wang/article/details/14166593