财神道app下载最新版本-财神到购彩大厅(彩世界)

热门关键词: 财神道app下载最新版本,财神到购彩大厅

javascript数据结构与算法--散列财神到购彩大厅

javascript数据结构与算法--散列

一:javascript数据结构与算法--散列

 一:什么是哈希表?

 

      哈希表也叫散列表,是根据关键码值(key,value)而直接进行访问的数据结构,它是通过键码值映射到表中一个位置来访问记录的,散列表后的数据可以快速的插入和使用,散列使用的数据结构叫做散列表。

 

 散列表的优点及缺点:

 

     优点:在散列表上插入,删除和取用数据都非常快。

 

     缺点:对于查找来说效率低下,比如查找一组数据中的最大值与最小值时候,这个时候我们可以使用二叉树查找了。

 

 散列表实现的具体原理?

 

散列函数的选择依赖于键值的数据类型,如果键是整型,那么散列函数就是以数组的长度对键取余。取余结果就当作数组的下标,将值存储在以该数字为下标的数组空间里。

如果键值是字符串类型,那么就将字符串中的每个字符的ASCLL码值相加起来,再对数组的长度取余。取余的结果当作数组的下标,将值存储在以该余数为下标的数组空间里面。

    一般情况下,散列函数会将每个键值映射为一个唯一的数组索引。然而,键的数量是无限的,数组的长度是有限的(在javascript上是这样的),那么我们的目标是想让散列函数尽量均匀地映射到数组中。使用散列函数时候,仍然会存在两个键(key)会映射到同一个值的可能。这种现象我们称为 ”碰撞”,为了避免 ”碰撞”,首先要确保散列表中用来存储数据的数组大小是个质数,因为这和计算散列值时使用的取余运算有关,并且希望数组的长度在100以上的质数,这是为了让数据在散列表中能均匀的分布,所以我们下面的数组长度先定义为137.

 

 散列表的取数据方法:

 

  当存储记录时,通过散列函数计算出记录的散列地址,当取记录时候,我们通过同样的散列函数计算记录的散列地址,并按此散列地址访问该记录。

 

散列基本含义如下图:

 

名字 散列函数(名字中每个字母的ASCLL码之和) 散列值 散列表

Durr 68 117 114 114 413

0

....

413 Durr

...

511 Smith

....

517 Jones

Smith 81 109 105 116 104 517

Jones 74 111 110 101 115 511

比如我们现在如果想要取Durr值得话,那么我们就可以取散列表中的第413记录 即可得到值。

 

二:代码如何实现HashTable类;

 

1.先实现HashTable类,定义一个属性,散列表的长度,如上所说,定义数组的长度为137.代码如下:

 

function HashTable() {

   this.table = new Array(137);

}

2.实现散列函数;

 

就将字符串中的每个字符的ASCLL码值相加起来,再对数组的长度取余。取余的结果当作数组的下标,将值存储在以该余数为下标的数组空间里面。代码如下:

 

 

function simpleHash (data) {

    var total = 0;

    for(var i = 0; i < data.length; i ) {

        total = data.charCodeAt(i);

    }

    console.log("Hash Value: " data " -> " total);

    return total % this.table.length;

}

 

 3. 将数据存入散列表。

 

function put(data){

    var pos = this.simpleHash(data);

    this.table[pos] = data;

}

 4. 显示散列表中的数据

 

 

function showDistro (){

    var n = 0;

    for(var i = 0; i < this.table.length; i ) {

        if(this.table[i] != undefined) {

         console.log(i ":" this.table[i]);

         }

     }

}

 

下面是所有的JS代码如下:

 

function HashTable() {

    this.table = new Array(137);

}

 

HashTable.prototype = {

    simpleHash: function(data) {

        var total = 0;

        for(var i = 0; i < data.length; i ) {

            total = data.charCodeAt(i);

        }

        console.log("Hash Value: " data " -> " total);

        return total % this.table.length;

    },

    put: function(data){

        var pos = this.simpleHash(data);

        this.table[pos] = data;

    },

    showDistro: function(){

        var n = 0;

        for(var i = 0; i < this.table.length; i ) {

            if(this.table[i] != undefined) {

                console.log(i ":" this.table[i]);

            }

        }

    }

};

 

我们先来做demo来测试下,如上面的代码;如下:

 

var someNames = ["David","Jennifer","Donnie","Raymond","Cynthia","Mike","Clayton","Danny","Jonathan"];

 

var hTable = new HashTable();

 

for(var i = 0; i < someNames.length; i) {

 

       hTable.put(someNames[i]);

 

}

 

hTable.showDistro(); 

 

 

 

simpleHash方法里面

 

 

 

 

 

 

上面可以看出,不同的键名(key),但是他们的值相同,由此发生了碰撞,所以最后一个值会存入散列表中。

 

二:一个更好的散列函数;

    为了避免碰撞,我们要有一个计算散列值的更好方法。霍纳算法很好地解决了这个问题,新的散列函数仍然先计算字符串中各字符的ASCLL码值,不过求和时每次要乘以一个质数。我们这里建议是31.代码如下:

 

 

function betterHash(string) {

    var H = 31;

    var total = 0;

    for(var i = 0; i < string.length; i) {

        total = H * total string.charCodeAt(i);

    }

    total = total % this.table.length;

    console.log("Hash Value: " string " -> " total);

    if(total < 0) {

        total = this.table.length - 1;

    }

    return parseInt(total);

 

但是我们的put的方法要改成如下了:

 

function put(data) {

   var pos = this.betterHash(data);

   this.table[pos] = data;

下面是所有的JS代码如下:

 

 

function HashTable() {

    this.table = new Array(137);

}

 

HashTable.prototype = {

    simpleHash: function(data) {

        var total = 0;

        for(var i = 0; i < data.length; i ) {

            total = data.charCodeAt(i);

        }

        console.log("Hash Value: " data " -> " total);

        return total % this.table.length;

    },

    

    put: function(data){

        //var pos = this.simpleHash(data);

        var pos = this.betterHash(data);

        this.table[pos] = data;

    },

    

    showDistro: function(){

        var n = 0;

        for(var i = 0; i < this.table.length; i ) {

            if(this.table[i] != undefined) {

                console.log(i ":" this.table[i]);

            }

        }

    },

    betterHash: function(string){

        var H = 31;

        var total = 0;

        for(var i = 0; i < string.length; i) {

            total = H * total string.charCodeAt(i);

        }

        total = total % this.table.length;

        console.log("Hash Value: " string " -> " total);

        if(total < 0) {

            total = this.table.length - 1;

        }

        return parseInt(total);

    }

};

 

var someNames = ["David","Jennifer","Donnie","Raymond","Cynthia","Mike","Clayton","Danny","Jonathan"];

var hTable = new HashTable();

for(var i = 0; i < someNames.length; i) {

    hTable.put(someNames[i]);

}

hTable.showDistro();

 

 

 

三:散列化整型键;

   上面我们展示了如何散列字符串类型的键,现在我们来看看如何散列化整型键,使用的数据是学生的成绩。我们将随机产生一个9位数的键,用以识别学生身份和一门成绩。

 

   代码如下:

 

 

function getRandomInt(min,max) {

    return Math.floor(Math.random() * (max - min 1)) min;

}

function genStuData(arr) {

    for(var i = 0; i < arr.length; i) {

        var num = "";

         for(var j = 1; j <= 9; j) {

             num = Math.floor(Math.random() * 10);

         }

         console.log(num);

         num = getRandomInt(50,100);

         console.log(num);

         arr[i] = num;

     }

}

 

使用getRandomInt()函数时,可以指定随机数的最大值与最小值。拿学生的成绩来看,最低分是50,最高分是100;

 

genStuData()函数生成学生的数据。里面的循环是用来生成学生的ID,紧跟在循环后面的代码生存一个随机成绩,并把成绩连在ID的后面。如下:

 

 

 

 

 

主程序会把ID和成绩分离。如下所示:

 

 

 

下面就是上面的测试代码如下:

 

 

var numStudents = 10;

var students = new Array(numStudents);

genStuData(students);

    

console.log("Student data: n");

for(var i = 0; i < students.length; i ) {

    console.log(students[i].substring(0,8) " " students[i].substring(9));

}

console.log("nnData distribution:n");

        

var hTable = new HashTable();

for(var i = 0; i < students.length; i ) {

    hTable.put(students[i]);

}

hTable.showDistro();

 

从散列表取值

 

   前面讲的是散列函数,现在我们要学会使用散列存取数据操作,现在我们需要修改put方法,使得该方法同时接受键和数据作为参数,对键值散列后,将数据存储到散列表中,如下put代码:

 

function put(key,data) {

    var pos = this.betterHash(key);

    this.table[pos] = data;

}

Put()方法将键值散列化后,将数据存储到散列化后的键值对应的数组中的位置上。

 

接下来我们定义get方法,用以读取存储在散列表中的数据。该方法同样需要对键值进行散列化,然后才能知道数据到底存储在数组的什么位置上。代码如下:

 

function get(key) {

    return this.table[this.betterHash(key)];

}

下面是所有的JS代码如下:

 

 

function HashTable() {

    this.table = new Array(137);

}

 

HashTable.prototype = {

    simpleHash: function(data) {

        var total = 0;

        for(var i = 0; i < data.length; i ) {

            total = data.charCodeAt(i);

        }

        console.log("Hash Value: " data " -> " total);

        return total % this.table.length;

    },

    

    put: function(key,data) {

        var pos = this.betterHash(key);

        this.table[pos] = data;

    },

    get: function(key) {

        return this.table[this.betterHash(key)];

    },

    showDistro: function(){

        var n = 0;

        for(var i = 0; i < this.table.length; i ) {

            if(this.table[i] != undefined) {

                console.log(i ":" this.table[i]);

            }

        }

    },

    betterHash: function(string){

        var H = 31;

        var total = 0;

        for(var i = 0; i < string.length; i) {

            total = H * total string.charCodeAt(i);

        }

        total = total % this.table.length;

        console.log("Hash Value: " string " -> " total);

        if(total < 0) {

            total = this.table.length - 1;

        }

        return parseInt(total);

    }

};

 

测试代码如下:

 

  var someNames = ["David","Jennifer","Donnie","Raymond","Cynthia","Mike","Clayton","Danny","Jonathan"];

var hTable = new HashTable();

for(var i = 0; i < someNames.length; i) {

    hTable.put(someNames[i],someNames[i]);

}

for(var i = 0; i < someNames.length; i) {

    console.log(hTable.get(someNames[i]));

}

 

四:碰撞处理

    当散列函数对于多个输入产生同样的输出时,就产生了碰撞。当碰撞发生时,我们仍然希望将键存储到通过散列算法产生的索引位置上,但是不可能将多份数据存储到一个数组单元中。那么实现开链法的方法是:在创建存储散列过的键值的数组时,通过调用一个函数创建一个新的空数组,然后在该数组赋值给散列表里的每个数组元素元素,这样就创建了一个二维数组,使用这种技术,即使两个键散列后的值相同,依然被保存在同样的位置上,但是他们的第二个数组的位置不一样。

 

 1下面我们通过如下方法来创建一个二维数组,我们也称这个数组为链。代码如下:

 

function buildChains(){

    for(var i = 0; i < this.table.length; i ) {

        this.table[i] = new Array();

    }

}

  2. 散列表里面使用多维数组存储数据,所以showDistro()方法代码需要改成如下:

 

 

function showDistro() {

  var n = 0;

  for(var i = 0; i < this.table.length; i ) {

    if(this.table[i][0] != undefined) {

        console.log(i ":" this.table[i]);

     }

    }

}

 

  3. 使用了开链法后,需要重新对put和get方法进行改造,put()方法实现原理如下:

 

    put()方法将键值散列,散列后的值对应数组中的一个位置,先尝试将数据放在该位置上的数组中的第一个单元格,如果该单元格里已经有数据了,put()方法会搜索下一个位置,直到找到能放置数据的单元格,并把数据存储进去,下面是put实现的代码:

 

 

function put(key,data) {

    var pos = this.simpleHash(key);

    var index = 0;

    if(this.table[pos][index] == undefined) {

        this.table[pos][index] = data;

    }else {

        while(this.table[pos][index] != undefined) {

            index;

        }

        this.table[pos][index] = data;

    }

}

 

   4.get() 方法先对键值散列,根据散列后的值找到散列表相应的位置,然后搜索该位置上的链,直到找到键值,如果找到,就将紧跟在键值后面的数据返回,如果没有找到,就返回undefined。代码如下:

 

 

function get(key) {

    var index = 0;

    var pos = this.simpleHash(key);

    if(this.table[pos][index] == key) {

        return this.table[pos][index];

    }else {

        while(this.table[pos][index] != key) {

            index;

        }

        return this.table[pos][index];

    }

    return undefined;

}

 

下面是实现开链法的所有JS代码如下:

 

 

function HashTable() {

    this.table = new Array(137);

}

 

HashTable.prototype = {

    simpleHash: function(data) {

        var total = 0;

        for(var i = 0; i < data.length; i ) {

            total = data.charCodeAt(i);

        }

        console.log("Hash Value: " data " -> " total);

        return total % this.table.length;

    },

    put: function(key,data) {

        var pos = this.simpleHash(key);

        var index = 0;

        if(this.table[pos][index] == undefined) {

            this.table[pos][index] = data;

        }else {

            while(this.table[pos][index] != undefined) {

                index;

            }

            this.table[pos][index] = data;

        }

    },

    get: function(key) {

        var index = 0;

        var pos = this.simpleHash(key);

        if(this.table[pos][index] == key) {

            return this.table[pos][index];

        }else {

            while(this.table[pos][index] != key) {

                index;

            }

            return this.table[pos][index];

        }

        return undefined;

    },

    showDistro: function(){

        var n = 0;

        for(var i = 0; i < this.table.length; i ) {

            if(this.table[i][0] != undefined) {

                console.log(i ":" this.table[i]);

            }

        }

    },

    buildChains: function() {

        for(var i = 0; i < this.table.length; i ) {

            this.table[i] = new Array();

        }

    }

};

 

 

var someNames = ["David","Jennifer","Donnie","Raymond","Cynthia","Mike","Clayton","Danny","Jonathan"];

var hTable = new HashTable();

hTable.buildChains();

 

for(var i = 0; i < someNames.length; i) {

     hTable.put(someNames[i],someNames[i]);

}

hTable.showDistro();

console.log("--------------------------");

for(var i = 0; i < someNames.length; i) {

      console.log("开链法 " i " " hTable.get(someNames[i]));

}

 

 

 

 

调用get()方法打印数据如下:

 

 

 

五:线性探测法

 基本原理:

 

   线性探测法属于一般的散列技术:开放寻址散列。当发生碰撞时,线性探测法检查散列表中的当前位置是否为空,如果为空,将数据存入该位置,如果不为空,则继续检查下一个位置,直到找到一个空的位置为止。

 

什么时候使用线性探测法,什么时候使用开链法呢?

 

如果数组的大小是待存储数据的个数是1.5倍,那么使用开链法,如果数组的大小是待存储的数据的2倍及2倍以上时,那么使用线性探测法。

 

为了实现线性探测法,我们需要增加一个新数组 values ,用来存储数据。代码如下:

 

function HashTable() {

     this.table = new Array(137);

     this.values = [];

}

我们知道探测法原理之后,我们就可以写put方法代码了,代码如下:

 

 

function put(key,data) {

    var pos = this.simpleHash(key);

    if(this.table[pos] == undefined) {

     this.table[pos] = key;

     this.values[pos] = data;

    }else {

     while(this.table[pos] != undefined) {

        pos;

     }

    this.table[pos] = key;

    this.values[pos] = data;

    }

}

 

2. get()方法的基本原理是:先搜索键在散列表中的位置,如果找到,则返回数组values中对应位置上的数据。如果没有找到,则循环搜索,以当前的位置的下一个位置开始循环搜索,如果找到对应的键,则返回对应的数据,否则的话 返回undefined;代码如下:

 

 

function get(key) {

    var pos = this.simpleHash(key);

    if(this.table[pos] == key) {

        return this.values[pos];

    }else {

        for(var i = pos 1; i < this.table.length; i ) {

        if(this.table[i] == key) {

            return this.values[i];

         }

        }

        }

    return undefined;

        

}

 

下面是所有JS代码如下:

 

 

function HashTable() {

    this.table = new Array(137);

    this.values = [];

}

 

HashTable.prototype = {

    simpleHash: function(data) {

        var total = 0;

        for(var i = 0; i < data.length; i ) {

            total = data.charCodeAt(i);

        }

        console.log("Hash Value: " data " -> " total);

        return total % this.table.length;

    },

    put: function(key,data) {

        var pos = this.simpleHash(key);

        if(this.table[pos] == undefined) {

            this.table[pos] = key;

            this.values[pos] = data;

        }else {

            while(this.table[pos] != undefined) {

                pos;

            }

            this.table[pos] = key;

            this.values[pos] = data;

        }

    },

    get: function(key) {

        var pos = this.simpleHash(key);

        if(this.table[pos] == key) {

            return this.values[pos];

        }else {

            for(var i = pos 1; i < this.table.length; i ) {

                if(this.table[i] == key) {

                    return this.values[i];

                }

            }

        }

        return undefined;

        

    },

    showDistro: function(){

        var n = 0;

        for(var i = 0; i < this.table.length; i ) {

            if(this.table[i] != undefined) {

                console.log(i ":" this.table[i]);

            }

        }

    }

};

 

var someNames = ["David","Jennifer","Donnie","Raymond","Cynthia","Mike","Clayton","Danny","Jonathan"];

var hTable = new HashTable();

        

for(var i = 0; i < someNames.length; i) {

    hTable.put(someNames[i],someNames[i]);

}

hTable.showDistro();

console.log("--------------------------");

        

for(var i = 0; i < someNames.length; i) {

    console.log(hTable.get(someNames[i]));

}

一:javascript数据结构与算法--散列 一:什么是哈希表? 哈希表也叫散列表,是根据关键码值(key,value)而直接...

扫盲:
1、console.log()与 console.dir()的区别
console.log()向web控制台输出一条消息.
console.dir()将一个JavaScript对象的属性和属性值显示成一个可交互的列表,点击折叠的小三角形可以查看各子属性的内容.
例:
console.log({f1: 'foo', f2: 'bar'})
// Object {f1: "foo", f2: "bar"}

 * --------------------------- scriptjava.util.ArrayList define enddd

 */ 

用面象对象的方式去使用javascript,性能比较差,但功能完善。 也许在使用javascript时,应该要更多的使...

参数赋值
var a = {
user:"追梦子",
fn:function(e,d,f){
console.log(this.user); //追梦子
console.log(e,d,f); //10 1 2
}}
var b = a.fn;
var c = b.bind(a,10);
c(1,2);
输出:追梦子
10 1 2(按照顺序来)

 * --------------------------- scriptjava.util.HashMap define start

 */ 
scriptjava.util.HashMap = function(configObj) { 
this._capacityDefault = 16; 
 
// config property default  
this._capacity = this._capacityDefault; 
this._loadFactor = 0.75; 
this._size = 0; 
this._maxLoop = 100; 
 
 
// config property custom  
if (arguments.length == 1 && typeof configObj == 'object') { 
for (property in configObj) { 
this['_' property] = configObj[property]; 


 
 
// config property other  
this._maxSize = parseInt(this._capacity * this._loadFactor); 
this._table = new Array(this._capacity); 

/*
 * the key-value element of HashMap this method will be overwrite by LinkedHashMap
 */ 
scriptjava.util.HashMap.prototype.Entry = function(key, value) { 
this.key = key, this.value = value, this.next = null 

 
 
/*
 * this method will be overwrite by LinkedHashMap
 */ 
scriptjava.util.HashMap.prototype._createEntry = function(key, value){ 
return new this.Entry(key, value); 

 
 
/*
 * this method will be overwrite by LinkedHashMap
 */ 
scriptjava.util.HashMap.prototype._addEntry = function(entry){ 
 

 
 
/*
 * this method will be overwrite by LinkedHashMap
 */ 
scriptjava.util.HashMap.prototype._recordAccess = function(entry){ 
 

 
 
/*
 * this method will be overwrite by LinkedHashMap
 */ 
scriptjava.util.HashMap.prototype._addEntry = function(entry){ 
 

 
 
//Returns an Array of the keys contained in this map.  
scriptjava.util.HashMap.prototype.keySet = function(){ 
scriptjava.log.info('HashMap.keySet()...'); 
var keyAry = new Array(this._size); 
for ( var i = 0; i < this._table.length; i ) { 
if (this._table[i] == undefined) { 
continue; 

var entryTemp = this._table[i]; 
while (entryTemp != null) { 
keyAry.push(entryTemp.key); 
entryTemp = entryTemp.next; 


return keyAry; 

 
 
/*
 * Removes all of the mappings from this map.
 * The map will be empty after this call returns.
 */ 
scriptjava.util.HashMap.prototype.clear = function(key, value) { 
// for ( var i = 0; i < this._table.length; i ) {  
// delete this._table[i];  
// }  
scriptjava.log.info('HashMap.clear()...'); 
this._capacity = this._capacityDefault; 
this._table = new Array(this._capacity); 
this._maxSize = parseInt(this._capacity * this._loadFactor); 
this._size = 0; 
 
if(this._head != undefined){ 
this._head = null; 

 
if(this._tail != undefined){ 
this._tail = null; 


 
 
/*
 * 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.
 */ 
scriptjava.util.HashMap.prototype.put = function(key, value) { 
var returnEntry = null; 
var findByKey = false; 
 
 
// rebuild map when need  
if (this._size == this._maxSize) { 
scriptjava.log.warn('WARNNING, Map is nearly full, size:' this._size

  • ', maxSize:' this._maxSize ', capacity:' this._capacity); 
    this._resize(); 

     
     
    var hash = this._reHash(scriptjava.util.hashCode(key)); 
    var indexOfKey = this._indexFor(hash, this._capacity); 
    scriptjava.log.info('Map.put(' key ',' value '),' 'indexOfKey:' indexOfKey); 
     
     
    var entryNew = this._createEntry(key, value); 
    returnEntry = entryNew; 
    // put the new entry on the right index of table  
    if (this._table[indexOfKey] == undefined) { 
    this._table[indexOfKey] = entryNew; 
    this._addEntry(entryNew); 
    } else { 
    // if key already exists, then update the value of this key  
    var alreadyExists = false; 
    var entryTemp = this._table[indexOfKey]; 
    while (entryTemp != null) { 
    if (entryTemp.key == key) { 
    alreadyExists = true; 
    findByKey = true; 
    entryTemp.value = value; 
    returnEntry = entryTemp; 
    break; 
    } else { 
    entryTemp = entryTemp.next; 


     
     
    if (!alreadyExists) { 
    entryNew.next = this._table[indexOfKey]; 
    this._table[indexOfKey] = entryNew; 
    this._addEntry(entryNew); 


     
     
    if (!findByKey) { 
    this._size ; 

     
    //the put() opretion will add new or update value, so, will always execute this._recordAccess()  
    if(this._accessOrderPut != undefined && this._accessOrderPut == true){ 
    this._recordAccess(entryNew); 

    return returnEntry; 

     
     
    /*
     * this method will be overwrite by LinkedHashMap
     */ 
    scriptjava.util.HashMap.prototype._removeEntry = function(entry){ 
     

     
     
    /*
     * Removes the mapping for the specified key from this map if present.
     */ 
    scriptjava.util.HashMap.prototype.remove = function(key) { 
    var returnEntry = null; 
    var hash = this._reHash(scriptjava.util.hashCode(key)); 
    var index = this._indexFor(hash, this._capacity); 
    var findByKey = false; 
     
     
    if (this._table[index] == undefined) { 
    return null; 
    } else { 
    var entryTemp = this._table[index]; 
    var entryTempPre = null; 
    while (entryTemp != null) { 
    if (entryTemp.key == key) { 
    findByKey = true; 
    returnEntry = entryTemp; 
     
     
    if (entryTempPre == null && entryTemp.next == null) { 
    // only one entry in this entryList  
    delete this._table[index]; 
    } else if (entryTempPre == null && entryTemp.next != null) { 
    // at least 2 entry in this entryList, and, is the head  
    this._table[index] = entryTemp.next; 
    } else if (entryTempPre != null && entryTemp.next == null) { 
    // at least 2 entry in this entryList, and, is the tail  
    entryTempPre.next = null; 
    } else { 
    // at least 3 entry in this entryList, and, is the middle  
    entryTempPre.next = entryTemp.next; 

     
     
    scriptjava.log.info('Map.romove(' key '), value:' (returnEntry == null ? null : returnEntry.value)); 
    this._removeEntry(entryTemp); 
    break; 

     
     
    entryTempPre = entryTemp; 
    entryTemp = entryTemp.next; 


     
     
    if (findByKey) { 
    this._size--; 

    return returnEntry; 

     
     
    /*
     * Returns the value to which the specified key is mapped, or null if this map contains no mapping for the key.
     */ 
    scriptjava.util.HashMap.prototype.get = function(key) { 
    var hash = this._reHash(scriptjava.util.hashCode(key)); 
    var index = this._indexFor(hash, this._capacity); 
     
     
    if (this._table[index] == undefined) { 
    return null; 
    } else { 
    var i = 0; 
    var valueFinal = null; 
    var entryTemp = this._table[index]; 
     
     
    while (entryTemp != null) { 
    i ; 
    if (i > this._maxLoop) { 
    break; 
    scriptjava.log.warn('too mach loops, performents will be down:' i); 

     
     
    if (entryTemp.key == key) { 
    valueFinal = entryTemp.value; 
    scriptjava.log.info('Map.get(' key '),' 'value:' valueFinal ',loops:' i); 
    this._recordAccess(entryTemp); 
    break; 
    } else { 
    entryTemp = entryTemp.next; 


     
     
    return valueFinal; 


     
     
    /*
     * Returns true if this map contains a mapping for the specified key.
     */ 
    scriptjava.util.HashMap.prototype.containsKey = function(key) { 
    var hash = this._reHash(scriptjava.util.hashCode(key)); 
    var index = this._indexFor(hash, this._capacity); 
     
     
    var contains = false; 
    if (this._table[index] == undefined) { 
    scriptjava.log.info('Map.containsKey(' key '), ' contains); 
    return contains; 

     
     
    var entryTemp = this._table[index]; 
    while (entryTemp != null) { 
    if (entryTemp.key == key) { 
    contains = true; 
    break; 
    } else { 
    entryTemp = entryTemp.next; 


     
     
    scriptjava.log.info('Map.containsKey(' key '), ' contains); 
    return contains; 

     
     
    /*
     * for each element of hashmap, call an costom function
     */ 
    scriptjava.util.HashMap.prototype.foreach = function(foreachFun) { 
    scriptjava.log.info('HashMap.foreach() start..............'); 
    for ( var i = 0; i < this._table.length; i ) { 
    if (this._table[i] == undefined) { 
    continue; 

    var entryTemp = this._table[i]; 
    while (entryTemp != null) { 
    foreachFun(entryTemp); 
    entryTemp = entryTemp.next; 


    scriptjava.log.info('HashMap.foreach() enddd..............'); 

     
     
    /*
     * Returns the number of key-value mappings in this map.
     */ 
    scriptjava.util.HashMap.prototype.size = function() { 
    scriptjava.log.info('Map.size(),' this._size); 
    return this._size; 

     
     
    /*
     * Returns true if this map contains a mapping for the specified key.
     */ 
    scriptjava.util.HashMap.prototype.isEmpty = function() { 
    return this._size == 0 ? true : false; 

     
     
    /*
     * 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
     * reaches its threshold.
     */ 
    scriptjava.util.HashMap.prototype._resize = function() { 
    var capacityNew = this._capacity * 2; 
    var maxSizeNew = parseInt(capacityNew * this._loadFactor); 
    var tableNew = new Array(capacityNew); 
     
     
    scriptjava.log.info('rebuild map,_capacity:' capacityNew); 
    scriptjava.log.info('rebuild map,_loadFactor:' this._loadFactor); 
    scriptjava.log.info('rebuild map,_maxSize:' maxSizeNew); 
     
     
    for ( var i = 0; i < this._table.length; i ) { 
    if (this._table[i] == undefined) { 
    continue; 

     
     
    var entryTemp = this._table[i]; 
    while (entryTemp != null) { 
    var hash = this._reHash(scriptjava.util.hashCode(entryTemp.key)); 
    var indexOfKey = this._indexFor(hash, capacityNew); 
    scriptjava.log.info('rebuild map, key:' entryTemp.key ', value:' entryTemp.value ', indexOfKey:' indexOfKey); 
     
     
    var entryNew = new this.Entry(entryTemp.key, entryTemp.value, null); 
    // put the new entry on the right index of table  
    if (tableNew[indexOfKey] == undefined) { 
    tableNew[indexOfKey] = entryNew; 
    } else { 
    entryNew.next = tableNew[indexOfKey]; 
    tableNew[indexOfKey] = entryNew; 

     
     
    entryTemp = entryTemp.next; 


     
     
    this._capacity = capacityNew; 
    this._maxSize = maxSizeNew; 
    this._table = tableNew; 

     
     
    scriptjava.util.HashMap.prototype._reHash = function(h) { 
    h ^= (h >>> 20) ^ (h >>> 12); 
    return h ^ (h >>> 7) ^ (h >>> 4); 

     
     
    scriptjava.util.HashMap.prototype._indexFor = function(h, length) { 
    return h & (length - 1); 

    /**
     * --------------------------- scriptjava.util.HashMap define enddd

 */ 
 
 
/**
 * --------------------------- scriptjava.util.LinkedHashMap define start ---------------------------
 */ 
scriptjava.util.LinkedHashMap = function(configObj){ 
//extends from scriptjava.util.HashMap  
scriptjava.util.HashMap.call(this); 
 
this._head = null; 
this._tail = null; 
//when true, the get() method will influce the access order  
this._accessOrder = false; 
//when true, the put() method will influce the access order alse, but it always be false  
this._accessOrderPut = false; 
 
// config property custom  
if (arguments.length == 1 && typeof configObj == 'object') { 
for (property in configObj) { 
this['_' property] = configObj[property]; 



 
 
//extends from scriptjava.util.HashMap  
scriptjava.util.LinkedHashMap.prototype = new scriptjava.util.HashMap(); 
scriptjava.util.LinkedHashMap.prototype.constructor = scriptjava.util.LinkedHashMap; 
 
 
// overwrite Entry  
scriptjava.util.LinkedHashMap.prototype.Entry = function(key, value) { 
this.key = key, this.value = value, this.next = null, this.before = null, this.after = null, this.count = 0; 

 
 
// overwrite _createEntry()  
scriptjava.util.LinkedHashMap.prototype._createEntry = function(key, value){ 
return new this.Entry(key, value); 

 
 
// overwrite _addEntry(), add an entry to the linkedlist tail  
scriptjava.util.LinkedHashMap.prototype._addEntry = function(entry){ 
if(this._head == null && this._tail == null){ 
this._head = entry; 
this._tail = entry; 
}else{ 
entry.before = this._tail; 
this._tail.after = entry; 
this._tail = entry; 


 
 
/*
 * remove an element from linkedlist
 */ 
scriptjava.util.LinkedHashMap.prototype._removeEntry = function(entry){ 
if(entry == this._head && entry.after == null){// only one entry  
this._head = null; 
this._tail = null; 
}else if(entry == this._head && entry.after != null){// at least two entry, and, the head  
this._head = entry.after; 
}else if(entry == this._tail){// at least two entry, and, the tail  
entry.before.after = null; 
this._tail = entry.before; 
}else{//at least three entry, and, the middle  
entry.before.after = entry.after; 
this._tail = entry.after; 


 
 
// overwrite _createEntry()  
scriptjava.util.LinkedHashMap.prototype._recordAccess = function(entry){ 
if(!this._accessOrder){ 
return; 

 
//linkedlist is empty  
if(this._head == null && this._tail == null){ 
this._head = entry; 
this._tail = entry; 
return; 

 
if(entry == this._head){ 
return; 

 
//the last one of linkedlist  
if(entry == this._tail && entry != this._head){ 
entry.before.after = entry.after; 
this._tail = entry.before; 
entry.before = null; 
entry.after = this._head; 
this._head.before = entry; 
this._head = entry; 
return; 

 
//middle of the linkedlist  
if(entry != this._head && entry != this._tail){ 
entry.before.after = entry.after; 
entry.after.before = entry.before; 
entry.after = this._head; 
entry.before = null; 
this._head.before = entry; 
this._head = entry; 
return; 


 
 
// overwrite _addEntry()  
scriptjava.util.LinkedHashMap.prototype.foreach = function(foreachFun){ 
scriptjava.log.info('LinkedHashMap.foreach() start...'); 
var tempEntry = this._head; 
while(tempEntry != null){ 
foreachFun(tempEntry); 
tempEntry = tempEntry.after; 

scriptjava.log.info('LinkedHashMap.foreach() enddd...'); 

/**
 * --------------------------- scriptjava.util.LinkedHashMap define enddd ---------------------------
 */ 
 
 
/**

console.dir({f1: 'foo', f2: 'bar'})
// Object
// f1: "foo"
// f2: "bar"
// proto: Object
上面代码显示dir方法的输出结果,比log方法更易读,信息也更丰富。
该方法对于输出DOM对象非常有用,因为会显示DOM对象的所有属性。
2、f.call()、 f.apply()、 f.bind()的区别
call() 方法调用一个函数, 其具有一个指定的this值和分别地提供的参数(参数的列表)。
apply()方法调用一个函数, 其具有一个指定的this值,以及作为一个数组(或[类似数组的对象]提供的参数。

[javascript]
/**
 * email:collon[email protected]
 * QQ:195358385
 */ 
var scriptjava = { 
log : { 
enable : false, 
consoleEnable : function() { 
return typeof console == 'undefined' ? false : true; 
}, 
info : function(message) { 
if (scriptjava.log.enable && scriptjava.log.consoleEnable()) { 
console.log(message); 
} else if(scriptjava.log.enable) { 
alert(message); 

}, 
warn : function(message) { 
if (scriptjava.log.enable) { 
console.warn(message); 


}, 
util : {} 

 
 
/*
 * null: return null '': return 0
 */ 
scriptjava.util.hashCode = function(str) { 
var hash = 0; 
 
 
if (arguments.length == 0) { 
throw new Error('number of arguments must > 1'); 

 
 
// null: return null '': return 0  
if (str == null || str == '') { 
return hash; 

 
 
// conver number to string  
if (typeof str == 'number') { 
str = new String(str); 

 
for ( var i = 0; i < str.length; i ) { 
hash = 31 * hash str.charCodeAt(i); 

 
 
return hash; 

 
 
/**

写于2017.07.29

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

  • f.length
    指形参的个数
  • f.call()
    f.call(this,argument[0],argument[1],argument[2],)
    例: function f ( ) {
    console.log(this)
    console.log(argiments)
    }
    执行f.call(1,2,3,4)
    则 f.this :1
    arguments : [2,3,4]
    每次调用都会创建新的this和arguments
  • 函数作用域
    var a
    function f1(){
    var a
    function f2(){
    a = 1(向上找,就是f1里面的var a
    }
    function f4(){
    var a
    }
    f2()
    f3()
    }
    function f3(){
    a = 2(向上找就是全局里面的var a)
    }
    先在自己作用域找,没有申明就向上找
    如果申明一个变量没有用var,且在整个作用域都没有申明,那么就是全局变量
    ③申明提升:提升到所在作用域的第一行

 

bind()方法创建一个新的函数, 当被调用时,将其this关键字设置为提供的值,在调用新函数时,在任何提供之前提供一个给定的参数序列。
bind() 函数会创建一个新函数(称为绑定函数),新函数与被调函数(绑定函数的目标函数)具有相同的函数体(在 ECMAScript 5 规范中内置的call 属性)。当新函数被调用时 this 值绑定到 bind() 的第一个参数,该参数不能被重写。绑定函数被调用时,bind() 也接受预设的参数提供给原函数。一个绑定函数也能使用new 操作符创建对象:这种行为就像把原函数当成构造器。提供的 this 值被忽略,同时调用时的参数被提供给模拟函数。
例:
var a = {
user:"追梦子",
fn:function(){
console.log(this.user);
}
}
var b = a.fn;
(console.log(b):
function(){
console.log(this.user);
})

var c = b.bind(a);(意味着c与a有相同的函数体,c调用a作为this)
console.log(c);
(function(){
console.log(this.user);
})

执行c( ) 打印出来“追梦子”

 * --------------------------- scriptjava.util.ArrayList define Start

 */ 
scriptjava.util.ArrayList = function(configObj){ 
this._capacityDefault= 16; 
 
// config property default  
this._capacity = this._capacityDefault; 
this._size = 0; 
 
 
// config property custom  
if (arguments.length == 1 && typeof configObj == 'object') { 
for (property in configObj) { 
this['_' property] = configObj[property]; 



/**

js声明变量方法

  • number(数值类型)
  • string(字符串)
  • boolean(布尔:FALSE、TRUE)
  • null(typeof null = “object”
  • symbol(产生一个与其他都不相等的值。typeof symbol ="symbol")
  • undefined(针对非对象类型为空的情况,typeof undefined = “undefined”)
  • object(对象类型)
    1、number
    js存储的数字大部分都是近似值,也就是说0.1 0.1(10次)!=1
  • NaN
    ① NaN代表一个目前无法表示的数字 typeof NaN = "number"
    ② NaN === NaN 值为FALSE,因为表示两个均不能表示的数字,值不相等
    ③ window.isNaN()方法判断一个东西是不是NaN,是一个全局API
    window.isNaN(“s”) 值为TRUE,因为首先会把字符串s转换为数字
    Number.isNaN("s")值为FALSE,因为它不转换直接判断
  • Infinity&-Infinity(正无穷大和负无穷大)
    ①window.isFinite()判断一个数字是否无穷大
  • 字符串转换为整数
    ① ‘1213243556’ 结果:1213243556
    ②window.ParseInt( ‘1213243556’ ,10) 结果:1213243556
  • 字符串转换为浮点数
    window.parseFloat('0.1233444') 结果:0.1233444
    2、字符串
  • 申明方法
    ① var s ="skdf"
    ② var s ='skdf'
    ③ var s =skdf(ES6语法:处理多行字符串,可回车)
  • 取变量内容的两种方法
    ① var name = 'frank'
    var s = 'hi' ' ' 'frank'
    console.log(s) : hi frank
    ② var name = 'frank'
    var s =hi, ${name}(这里可以加多个变量)
    console.log(s) : hi, frank
  • 其他注意事项
    ① "s" "d" : "sd";1 "2" : "12"(只要有1个是字符串,就都转换为字符串)
    ②var s = 'abcd'
    s[0]="a"; s[1]="b"
    不能对任意一个赋值,如s[0]="7"是无效的
    s.length代表的是字符串的个数
    3、对象
    比较特殊的对象:数组、函数
    简单类型与复杂类型的区别:在内存中占得位数是否确定
  • 对象建立方法
    ①var a ={ }
    ②var a = new object();
    ③var a =Object.create(object.prototype)
    var object = {
    key1:value1;
    key2:value2;
    }
  • 关于key
    ①object.keys( ) 打出对象所有的key
    ②key可以叫做属性或者方法
    ③key的类型是字符串
    4、数组
  • 生成数组
    ① var a =[ ]
    ② var a = new Array[10](表示一个长度为10的数组)
    5、函数
  • 申明方法
    ① function a (p1,p2,p3){ }(申明会提升)
    ② var f =function(){ } (不会提升;相当于var f; f =function(){ })
  • 函数返回值
    ① function f3 ( ){
    function f4( ){
    return 2
    }
    var a =1
    return f4( ) /return f4
    }

apply与 call()非常相似,不同之处在于提供参数的方式。apply
使用参数数组而不是一组参数列表(原文:a named set of parameters)。apply 可以使用数组字面量(array literal),如 fun.apply(this, ['eat', 'bananas']),或数组对象, 如 fun.apply(this, new Array('eat', 'bananas'))。你也可以使用 arguments 对象作为 argsArray参数。 arguments是一个函数的局部变量。 它可以被用作被调用对象的所有未指定的参数。 这样,你在使用apply函数的时候就不需要知道被调用对象的所有参数。 你可以使用arguments来把所有的参数传递给被调用对象。 被调用对象接下来就负责处理这些参数。
function keith(a, b) {
console.log(a b);
}
keith.call(null, 2, 3); //5
keith.apply(null, [2, 3]); //5
应用1:找出数组里最大的数:
var a = [2, 4, 5, 7, 8, 10];
console.log(Math.max.apply(null, a)); //10
console.log(Math.max.call(null,2, 4, 5, 7, 8, 10)); //10
应用2:将数组的空元素变为undefined
通过apply方法,利用Array构造函数将数组的空元素变成undefined。
console.log(Array.apply(null, [1, , 3])); // [1, undefined, 3]
空元素与undefined的差别在于,数组的forEach方法会跳过空元素,但是不会跳过undefined和null。因此,遍历内部元素的时候,会得到不同的结果。
var
a = [1, , 3];
a.forEach(
function(index) {
console.log(index);
//1,3 ,跳过了空元素。
})
Array.apply(null,a).forEach(
function(index){console.log(index);
////1,undefined,3 ,将空元素设置为undefined
})
应用3:转换类似数组的对象
另外,利用数组对象的slice方法,可以将一个类似数组的对象(比如arguments对象)转为真正的数组。当然,slice方法的一个重要应用,就是将类似数组的对象转为真正的数组。call和apply都可以实现该应用。
console.log(Array.prototype.slice.apply({0:1,length:1}));
//[1]
console.log(Array.prototype.slice.call({0:1,length:1}));
//[1]
console.log(Array.prototype.slice.apply({0:1,length:2}));
//[1,undefined]
console.log(Array.prototype.slice.call({0:1,length:2}));
//[1,undefined]
function
keith(a,b,c){
return arguments;
}
console.log(Array.prototype.slice.call(keith(2,3,4)));
//[2,3,4]

js7种基本数据类型

  • var a =1
    表示声明一个变量。用var声明的变量都存在声明提升,意思就是声明在前,赋值在后。
    上述等价于:var a ; a=1
    同样在一个作用域里面,如果你写:a=1;var a ;等价于var a ; a=1
  • let b =2
    let对应var,它只在当前作用域有效,而不会声明提升
  • const c =3
    const用于声明常量,声明的时候需赋值,同时不能再次更改值
  • d=1
    这样声明在顶级作用域就是全局变量global.d。

return f4( ) 与return f4的区别:f4( ) ===2;f4===“function f4( ){
return 2
}”

② var f =function(){ } (不会提升;相当于var f; f =function(){ })

上面代码的call,apply方法的参数都是对象,但是返回结果都是数组,这就起到了将对象转成数组的目的。从上面代码可以看到,这个方法起作用的前提是,被处理的对象必须有length属性,以及相对应的数字键。


财神到购彩大厅 1

image.png

本文由财神道app下载最新版本发布于web前端,转载请注明出处:javascript数据结构与算法--散列财神到购彩大厅