散列

作者: _____西班木有蛀牙 | 来源:发表于2018-07-01 19:22 被阅读13次

散列 & 线性散列
python数据结构教程 Day10
散列
散列
散列
散列
散列
散列
散列
散列

// 通过将字符串的ASCII码值的和来计算hash值
// 缺点：hash值分配不均匀
<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <title>链表</title>
</head>

<body>
<script>
    // hash
    function HashTable () {
        this.table = new Array(137);
        this.simpleHash = simpleHash;
        this.showDistro = showDistro;
        this.put = put;
        this.get = get;
    }

    function simpleHash (data) {
        var total = 0;
        for (var i = 0; i < data.length;i++) {
            total += data.charCodeAt(i);
        }
        return total % this.table.length;
    }

    
    // 插入
    function put (data) {
        var pos = this.simpleHash(data);
        this.table[pos] = data;
    }

    function get (key) {
        return this.table[this.simpleHash(data)];
    }

    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] + '】')
            }
        }
    }

    var hTable = new HashTable();
    hTable.put('china');
    hTable.put('Japan');
    hTable.put('America');
    hTable.put('nicha');
    hTable.put('131');
    hTable.put('78');
    hTable.put('39');
    hTable.put('460');
    hTable.showDistro();
</script>
</body>

</html>

<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <title>链表</title>
</head>

<body>
<script>
    // hash
    function HashTable () {
        this.table = new Array(137);
        this.simpleHash = simpleHash;
        this.betterHash = betterHash;
        this.showDistro = showDistro;
        this.put = put;
        this.get = get;
    }
    
    function simpleHash (data) {
        var total = 0;
        for (var i = 0; i < data.length;i++) {
            total += data.charCodeAt(i);
        }
        return total % this.table.length;
    }

    function betterHash (data) {
        var H = 31;
        var total = 0;
        for (var i = 0; i < data.length; i++) {
            total += H * total + data.charCodeAt(i);
        }
        if (total < 0) {
            total += this.table.length - 1;
        }
        return total % this.table.length;
    }

    // 插入
    function put (data) {
        // var pos = this.simpleHash(data);
        var pos = this.betterHash(data);
        this.table[pos] = data;
    }

    function get (key) {
        return this.table[this.simpleHash(data)];
    }

    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] + '】')
            }
        }
    }

    var hTable = new HashTable();
    hTable.put('china');
    hTable.put('Japan');
    hTable.put('America');
    hTable.put('nicha');
    hTable.put('131');
    hTable.put('78');
    hTable.put('39');
    hTable.put('460');
    hTable.showDistro();
</script>
</body>

</html>

// 开链法，把一维数组转换为二维数组
<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <title>链表</title>
</head>

<body>
<script>
    // hash
    function HashTable () {
        this.table = new Array(137);
        this.buildChians = buildChians;
        this.simpleHash = simpleHash;
        this.betterHash = betterHash;
        this.showDistro = showDistro;
        this.put = put;
        this.get = get;
    }
    
    function buildChians () {
        for (var i = 0; i < this.table.length; i++) {
            this.table[i] = new Array();
        }
    }

    function simpleHash (data) {
        var total = 0;
        for (var i = 0; i < data.length;i++) {
            total += data.charCodeAt(i);
        }
        return total % this.table.length;
    }

    function betterHash (data) {
        var H = 31;
        var total = 0;
        for (var i = 0; i < data.length; i++) {
            total += H * total + data.charCodeAt(i);
        }
        if (total < 0) {
            total += this.table.length - 1;
        }
        return total % this.table.length;
    }

    // 插入
    function put (data) {
        var pos = this.simpleHash(data);
        // var pos = this.betterHash(data);
        // this.table[pos] = data;
        var index = 0;
        if (this.table[pos][index] == undefined) {
            this.table[pos][index] = data;
            index ++;
        } else {
            while (this.table[pos][index] != undefined) {
                ++index;
            }
            this.table[pos][index] = data;
        }
    }

    function get (key) {
        return this.table[this.simpleHash(data)];
    }

    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] + '】')
            }
        }
    }

    var hTable = new HashTable();
    hTable.buildChians();
    hTable.put('china');
    hTable.put('Japan');
    hTable.put('America');
    hTable.put('nicha');
    hTable.showDistro();
</script>
</body>

</html>

<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <title>链表</title>
</head>

<body>
<script>
    // hash
    function HashTable () {
        this.table = new Array(137);
        this.simpleHash = simpleHash;
        this.showDistro = showDistro;
        this.put = put;
        this.get = get;
    }

    function simpleHash (data) {
        var total = 0;
        for (var i = 0; i < data.length;i++) {
            total += data.charCodeAt(i);
        }
        return total % this.table.length;
    }
    
    // 插入
    function put (data) {
        var pos = this.simpleHash(data);
        // this.table[pos] = data;
        if (this.table[pos] == undefined) {
            this.table[pos] = data;
        } else {
            while (this.table[pos] != undefined) {
                pos++;
            }
            this.table[pos] = data;
        }
    }

    function get (key) {
        var hash = this.simpleHash(key);
        console.log(hash);
        for (var i = hash; i < this.table.length; i++) {
            if (this.table[i] == key) {
                return i;
            }
        }
        return undefined;
    }

    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] + '】')
            }
        }
    }

    var hTable = new HashTable();
    hTable.put('china');
    hTable.put('Japan');
    hTable.put('America');
    hTable.put('nicha');
    console.log(hTable.get('nicha'))
    hTable.showDistro();
</script>
</body>

</html>