javascript实现原生的Java版本的HashMap及LinkedHashMap

javascript实现原生的HashMap及LinkedHashMap
用面象对象的方式去使用javascript,性能比较差,但功能完善。
也许在使用javascript时,应该要更多的使用该语言本身的特性。

 

[javascript] 

  1. /**
  2.  * email:collonn@126.com
  3.  * QQ:195358385
  4.  */
  5. var scriptjava = {
  6. log : {
  7. enable : false,
  8. consoleEnable : function() {
  9. return typeof console == ‘undefined’ ? false : true;
  10. },
  11. info : function(message) {
  12. if (scriptjava.log.enable && scriptjava.log.consoleEnable()) {
  13. console.log(message);
  14. } else if(scriptjava.log.enable) {
  15. alert(message);
  16. }
  17. },
  18. warn : function(message) {
  19. if (scriptjava.log.enable) {
  20. console.warn(message);
  21. }
  22. }
  23. },
  24. util : {}
  25. }
  26. /*
  27.  * null: return null ”: return 0
  28.  */
  29. scriptjava.util.hashCode = function(str) {
  30. var hash = 0;
  31. if (arguments.length == 0) {
  32. throw new Error(‘number of arguments must > 1’);
  33. }
  34. // null: return null ”: return 0
  35. if (str == null || str == ”) {
  36. return hash;
  37. }
  38. // conver number to string
  39. if (typeof str == ‘number’) {
  40. str = new String(str);
  41. }
  42. for ( var i = 0; i < str.length; i++) {
  43. hash = 31 * hash + str.charCodeAt(i);
  44. }
  45. return hash;
  46. }
  47. /**
  48.  * ————————— scriptjava.util.HashMap define start —————————
  49.  */
  50. scriptjava.util.HashMap = function(configObj) {
  51. this._capacityDefault = 16;
  52. // config property default
  53. this._capacity = this._capacityDefault;
  54. this._loadFactor = 0.75;
  55. this._size = 0;
  56. this._maxLoop = 100;
  57. // config property custom
  58. if (arguments.length == 1 && typeof configObj == ‘object’) {
  59. for (property in configObj) {
  60. this[‘_’ + property] = configObj[property];
  61. }
  62. }
  63. // config property other
  64. this._maxSize = parseInt(this._capacity * this._loadFactor);
  65. this._table = new Array(this._capacity);
  66. }
  67. /*
  68.  * the key-value element of HashMap this method will be overwrite by LinkedHashMap
  69.  */
  70. scriptjava.util.HashMap.prototype.Entry = function(key, value) {
  71. this.key = key, this.value = value, this.next = null
  72. }
  73. /*
  74.  * this method will be overwrite by LinkedHashMap
  75.  */
  76. scriptjava.util.HashMap.prototype._createEntry = function(key, value){
  77. return new this.Entry(key, value);
  78. }
  79. /*
  80.  * this method will be overwrite by LinkedHashMap
  81.  */
  82. scriptjava.util.HashMap.prototype._addEntry = function(entry){
  83. }
  84. /*
  85.  * this method will be overwrite by LinkedHashMap
  86.  */
  87. scriptjava.util.HashMap.prototype._recordAccess = function(entry){
  88. }
  89. /*
  90.  * this method will be overwrite by LinkedHashMap
  91.  */
  92. scriptjava.util.HashMap.prototype._addEntry = function(entry){
  93. }
  94. //Returns an Array of the keys contained in this map.
  95. scriptjava.util.HashMap.prototype.keySet = function(){
  96. scriptjava.log.info(‘HashMap.keySet()…’);
  97. var keyAry = new Array(this._size);
  98. for ( var i = 0; i < this._table.length; i++) {
  99. if (this._table[i] == undefined) {
  100. continue;
  101. }
  102. var entryTemp = this._table[i];
  103. while (entryTemp != null) {
  104. keyAry.push(entryTemp.key);
  105. entryTemp = entryTemp.next;
  106. }
  107. }
  108. return keyAry;
  109. }
  110. /*
  111.  * Removes all of the mappings from this map.
  112.  * The map will be empty after this call returns.
  113.  */
  114. scriptjava.util.HashMap.prototype.clear = function(key, value) {
  115. // for ( var i = 0; i < this._table.length; i++) {
  116. // delete this._table[i];
  117. // }
  118. scriptjava.log.info(‘HashMap.clear()…’);
  119. this._capacity = this._capacityDefault;
  120. this._table = new Array(this._capacity);
  121. this._maxSize = parseInt(this._capacity * this._loadFactor);
  122. this._size = 0;
  123. if(this._head != undefined){
  124. this._head = null;
  125. }
  126. if(this._tail != undefined){
  127. this._tail = null;
  128. }
  129. }
  130. /*
  131.  * Associates the specified value with the specified key in this map. If the map previously contained a mapping for the key, the old value is replaced.
  132.  */
  133. scriptjava.util.HashMap.prototype.put = function(key, value) {
  134. var returnEntry = null;
  135. var findByKey = false;
  136. // rebuild map when need
  137. if (this._size == this._maxSize) {
  138. scriptjava.log.warn(‘WARNNING, Map is nearly full, size:’ + this._size + ‘, maxSize:’ + this._maxSize + ‘, capacity:’ + this._capacity);
  139. this._resize();
  140. }
  141. var hash = this._reHash(scriptjava.util.hashCode(key));
  142. var indexOfKey = this._indexFor(hash, this._capacity);
  143. scriptjava.log.info(‘Map.put(‘ + key + ‘,’ + value + ‘),’ + ‘indexOfKey:’ + indexOfKey);
  144. var entryNew = this._createEntry(key, value);
  145. returnEntry = entryNew;
  146. // put the new entry on the right index of table
  147. if (this._table[indexOfKey] == undefined) {
  148. this._table[indexOfKey] = entryNew;
  149. this._addEntry(entryNew);
  150. } else {
  151. // if key already exists, then update the value of this key
  152. var alreadyExists = false;
  153. var entryTemp = this._table[indexOfKey];
  154. while (entryTemp != null) {
  155. if (entryTemp.key == key) {
  156. alreadyExists = true;
  157. findByKey = true;
  158. entryTemp.value = value;
  159. returnEntry = entryTemp;
  160. break;
  161. } else {
  162. entryTemp = entryTemp.next;
  163. }
  164. }
  165. if (!alreadyExists) {
  166. entryNew.next = this._table[indexOfKey];
  167. this._table[indexOfKey] = entryNew;
  168. this._addEntry(entryNew);
  169. }
  170. }
  171. if (!findByKey) {
  172. this._size++;
  173. }
  174. //the put() opretion will add new or update value, so, will always execute this._recordAccess()
  175. if(this._accessOrderPut != undefined && this._accessOrderPut == true){
  176. this._recordAccess(entryNew);
  177. }
  178. return returnEntry;
  179. }
  180. /*
  181.  * this method will be overwrite by LinkedHashMap
  182.  */
  183. scriptjava.util.HashMap.prototype._removeEntry = function(entry){
  184. }
  185. /*
  186.  * Removes the mapping for the specified key from this map if present.
  187.  */
  188. scriptjava.util.HashMap.prototype.remove = function(key) {
  189. var returnEntry = null;
  190. var hash = this._reHash(scriptjava.util.hashCode(key));
  191. var index = this._indexFor(hash, this._capacity);
  192. var findByKey = false;
  193. if (this._table[index] == undefined) {
  194. return null;
  195. } else {
  196. var entryTemp = this._table[index];
  197. var entryTempPre = null;
  198. while (entryTemp != null) {
  199. if (entryTemp.key == key) {
  200. findByKey = true;
  201. returnEntry = entryTemp;
  202. if (entryTempPre == null && entryTemp.next == null) {
  203. // only one entry in this entryList
  204. delete this._table[index];
  205. } else if (entryTempPre == null && entryTemp.next != null) {
  206. // at least 2 entry in this entryList, and, is the head
  207. this._table[index] = entryTemp.next;
  208. } else if (entryTempPre != null && entryTemp.next == null) {
  209. // at least 2 entry in this entryList, and, is the tail
  210. entryTempPre.next = null;
  211. } else {
  212. // at least 3 entry in this entryList, and, is the middle
  213. entryTempPre.next = entryTemp.next;
  214. }
  215. scriptjava.log.info(‘Map.romove(‘ + key + ‘), value:’ + (returnEntry == null ? null : returnEntry.value));
  216. this._removeEntry(entryTemp);
  217. break;
  218. }
  219. entryTempPre = entryTemp;
  220. entryTemp = entryTemp.next;
  221. }
  222. }
  223. if (findByKey) {
  224. this._size–;
  225. }
  226. return returnEntry;
  227. }
  228. /*
  229.  * Returns the value to which the specified key is mapped, or null if this map contains no mapping for the key.
  230.  */
  231. scriptjava.util.HashMap.prototype.get = function(key) {
  232. var hash = this._reHash(scriptjava.util.hashCode(key));
  233. var index = this._indexFor(hash, this._capacity);
  234. if (this._table[index] == undefined) {
  235. return null;
  236. } else {
  237. var i = 0;
  238. var valueFinal = null;
  239. var entryTemp = this._table[index];
  240. while (entryTemp != null) {
  241. i++;
  242. if (i > this._maxLoop) {
  243. break;
  244. scriptjava.log.warn(‘too mach loops, performents will be down:’ + i);
  245. }
  246. if (entryTemp.key == key) {
  247. valueFinal = entryTemp.value;
  248. scriptjava.log.info(‘Map.get(‘ + key + ‘),’ + ‘value:’ + valueFinal + ‘,loops:’ + i);
  249. this._recordAccess(entryTemp);
  250. break;
  251. } else {
  252. entryTemp = entryTemp.next;
  253. }
  254. }
  255. return valueFinal;
  256. }
  257. }
  258. /*
  259.  * Returns true if this map contains a mapping for the specified key.
  260.  */
  261. scriptjava.util.HashMap.prototype.containsKey = function(key) {
  262. var hash = this._reHash(scriptjava.util.hashCode(key));
  263. var index = this._indexFor(hash, this._capacity);
  264. var contains = false;
  265. if (this._table[index] == undefined) {
  266. scriptjava.log.info(‘Map.containsKey(‘ + key + ‘), ‘ + contains);
  267. return contains;
  268. }
  269. var entryTemp = this._table[index];
  270. while (entryTemp != null) {
  271. if (entryTemp.key == key) {
  272. contains = true;
  273. break;
  274. } else {
  275. entryTemp = entryTemp.next;
  276. }
  277. }
  278. scriptjava.log.info(‘Map.containsKey(‘ + key + ‘), ‘ + contains);
  279. return contains;
  280. }
  281. /*
  282.  * for each element of hashmap, call an costom function
  283.  */
  284. scriptjava.util.HashMap.prototype.foreach = function(foreachFun) {
  285. scriptjava.log.info(‘HashMap.foreach() start…………..’);
  286. for ( var i = 0; i < this._table.length; i++) {
  287. if (this._table[i] == undefined) {
  288. continue;
  289. }
  290. var entryTemp = this._table[i];
  291. while (entryTemp != null) {
  292. foreachFun(entryTemp);
  293. entryTemp = entryTemp.next;
  294. }
  295. }
  296. scriptjava.log.info(‘HashMap.foreach() enddd…………..’);
  297. }
  298. /*
  299.  * Returns the number of key-value mappings in this map.
  300.  */
  301. scriptjava.util.HashMap.prototype.size = function() {
  302. scriptjava.log.info(‘Map.size(),’ + this._size);
  303. return this._size;
  304. }
  305. /*
  306.  * Returns true if this map contains a mapping for the specified key.
  307.  */
  308. scriptjava.util.HashMap.prototype.isEmpty = function() {
  309. return this._size == 0 ? true : false;
  310. }
  311. /*
  312.  * Rehashes the contents of this map into a new array with a larger capacity. This method is called automatically when the number of keys in this map
  313.  * reaches its threshold.
  314.  */
  315. scriptjava.util.HashMap.prototype._resize = function() {
  316. var capacityNew = this._capacity * 2;
  317. var maxSizeNew = parseInt(capacityNew * this._loadFactor);
  318. var tableNew = new Array(capacityNew);
  319. scriptjava.log.info(‘rebuild map,_capacity:’ + capacityNew);
  320. scriptjava.log.info(‘rebuild map,_loadFactor:’ + this._loadFactor);
  321. scriptjava.log.info(‘rebuild map,_maxSize:’ + maxSizeNew);
  322. for ( var i = 0; i < this._table.length; i++) {
  323. if (this._table[i] == undefined) {
  324. continue;
  325. }
  326. var entryTemp = this._table[i];
  327. while (entryTemp != null) {
  328. var hash = this._reHash(scriptjava.util.hashCode(entryTemp.key));
  329. var indexOfKey = this._indexFor(hash, capacityNew);
  330. scriptjava.log.info(‘rebuild map, key:’ + entryTemp.key + ‘, value:’ + entryTemp.value + ‘, indexOfKey:’ + indexOfKey);
  331. var entryNew = new this.Entry(entryTemp.key, entryTemp.value, null);
  332. // put the new entry on the right index of table
  333. if (tableNew[indexOfKey] == undefined) {
  334. tableNew[indexOfKey] = entryNew;
  335. } else {
  336. entryNew.next = tableNew[indexOfKey];
  337. tableNew[indexOfKey] = entryNew;
  338. }
  339. entryTemp = entryTemp.next;
  340. }
  341. }
  342. this._capacity = capacityNew;
  343. this._maxSize = maxSizeNew;
  344. this._table = tableNew;
  345. }
  346. scriptjava.util.HashMap.prototype._reHash = function(h) {
  347. h ^= (h >>> 20) ^ (h >>> 12);
  348. return h ^ (h >>> 7) ^ (h >>> 4);
  349. }
  350. scriptjava.util.HashMap.prototype._indexFor = function(h, length) {
  351. return h & (length – 1);
  352. }
  353. /**
  354.  * ————————— scriptjava.util.HashMap define enddd —————————
  355.  */
  356. /**
  357.  * ————————— scriptjava.util.LinkedHashMap define start —————————
  358.  */
  359. scriptjava.util.LinkedHashMap = function(configObj){
  360. //extends from scriptjava.util.HashMap
  361. scriptjava.util.HashMap.call(this);
  362. this._head = null;
  363. this._tail = null;
  364. //when true, the get() method will influce the access order
  365. this._accessOrder = false;
  366. //when true, the put() method will influce the access order alse, but it always be false
  367. this._accessOrderPut = false;
  368. // config property custom
  369. if (arguments.length == 1 && typeof configObj == ‘object’) {
  370. for (property in configObj) {
  371. this[‘_’ + property] = configObj[property];
  372. }
  373. }
  374. }
  375. //extends from scriptjava.util.HashMap
  376. scriptjava.util.LinkedHashMap.prototype = new scriptjava.util.HashMap();
  377. scriptjava.util.LinkedHashMap.prototype.constructor = scriptjava.util.LinkedHashMap;
  378. // overwrite Entry
  379. scriptjava.util.LinkedHashMap.prototype.Entry = function(key, value) {
  380. this.key = key, this.value = value, this.next = null, this.before = null, this.after = null, this.count = 0;
  381. }
  382. // overwrite _createEntry()
  383. scriptjava.util.LinkedHashMap.prototype._createEntry = function(key, value){
  384. return new this.Entry(key, value);
  385. }
  386. // overwrite _addEntry(), add an entry to the linkedlist tail
  387. scriptjava.util.LinkedHashMap.prototype._addEntry = function(entry){
  388. if(this._head == null && this._tail == null){
  389. this._head = entry;
  390. this._tail = entry;
  391. }else{
  392. entry.before = this._tail;
  393. this._tail.after = entry;
  394. this._tail = entry;
  395. }
  396. }
  397. /*
  398.  * remove an element from linkedlist
  399.  */
  400. scriptjava.util.LinkedHashMap.prototype._removeEntry = function(entry){
  401. if(entry == this._head && entry.after == null){// only one entry
  402. this._head = null;
  403. this._tail = null;
  404. }else if(entry == this._head && entry.after != null){// at least two entry, and, the head
  405. this._head = entry.after;
  406. }else if(entry == this._tail){// at least two entry, and, the tail
  407. entry.before.after = null;
  408. this._tail = entry.before;
  409. }else{//at least three entry, and, the middle
  410. entry.before.after = entry.after;
  411. this._tail = entry.after;
  412. }
  413. }
  414. // overwrite _createEntry()
  415. scriptjava.util.LinkedHashMap.prototype._recordAccess = function(entry){
  416. if(!this._accessOrder){
  417. return;
  418. }
  419. //linkedlist is empty
  420. if(this._head == null && this._tail == null){
  421. this._head = entry;
  422. this._tail = entry;
  423. return;
  424. }
  425. if(entry == this._head){
  426. return;
  427. }
  428. //the last one of linkedlist
  429. if(entry == this._tail && entry != this._head){
  430. entry.before.after = entry.after;
  431. this._tail = entry.before;
  432. entry.before = null;
  433. entry.after = this._head;
  434. this._head.before = entry;
  435. this._head = entry;
  436. return;
  437. }
  438. //middle of the linkedlist
  439. if(entry != this._head && entry != this._tail){
  440. entry.before.after = entry.after;
  441. entry.after.before = entry.before;
  442. entry.after = this._head;
  443. entry.before = null;
  444. this._head.before = entry;
  445. this._head = entry;
  446. return;
  447. }
  448. }
  449. // overwrite _addEntry()
  450. scriptjava.util.LinkedHashMap.prototype.foreach = function(foreachFun){
  451. scriptjava.log.info(‘LinkedHashMap.foreach() start…’);
  452. var tempEntry = this._head;
  453. while(tempEntry != null){
  454. foreachFun(tempEntry);
  455. tempEntry = tempEntry.after;
  456. }
  457. scriptjava.log.info(‘LinkedHashMap.foreach() enddd…’);
  458. }
  459. /**
  460.  * ————————— scriptjava.util.LinkedHashMap define enddd —————————
  461.  */
  462. /**
  463.  * ————————— scriptjava.util.ArrayList define Start —————————
  464.  */
  465. scriptjava.util.ArrayList = function(configObj){
  466. this._capacityDefault= 16;
  467. // config property default
  468. this._capacity = this._capacityDefault;
  469. this._size = 0;
  470. // config property custom
  471. if (arguments.length == 1 && typeof configObj == ‘object’) {
  472. for (property in configObj) {
  473. this[‘_’ + property] = configObj[property];
  474. }
  475. }
  476. }
  477. /**
  478.  * ————————— scriptjava.util.ArrayList define enddd —————————
  479.  */

标签