文档章节

基于拉链法的散列表

gaomq
 gaomq
发布于 2017/07/20 08:49
字数 284
阅读 9
收藏 0

1.首先实现一个链表。注意链表结点的插入实现。是头插法。

public class SequentialSearchST<Key, Value> {
    private Node first;

    private class Node {
        Key key;
        Value value;
        Node next;

        public Node(Key key, Value value, Node next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    public Value get(Key key) {
        Node node = first;
        while (node != null) {
            if (node.key.equals(key)) {
                return node.value;
            }
        }
        return null;
    }

    public void put(Key key, Value value) {
        for (Node x = first; x != null; x = x.next) {
            if (x.key.equals(key)) {
                x.value = value;
                return;
            }
        }
        first = new Node(key, value, first);
    }
}

/**
 * 基于拉链法的散列表
 * 
 * @author gao.mq
 *
 * @param <Key>
 * @param <Value>
 */
public class SeparateChainingHashST<Key, Value> {
    private int N; // 键值对总数
    private int M; // 散列表的大小
    private SequentialSearchST<Key, Value>[] st;// 存放链表对象的数组

    public SeparateChainingHashST() {
        this(997);
    }

    public SeparateChainingHashST(int M) {
        // 创建M条链表
        this.M = M;
        st = (SequentialSearchST<Key, Value>[]) new SequentialSearchST[M];
        for (int i = 0; i < M; i++) {
            st[i] = new SequentialSearchST<Key, Value>();
        }
    }

    // 计算映射在数组上的位置
    private int hash(Key key) {
        return (key.hashCode() & 0x7fffffff) % M;
    }

    public Value get(Key key) {
        // 根据映射到数组上的位置找到链表
        return st[hash(key)].get(key);
    }

    public void put(Key key, Value value) {
        st[hash(key)].put(key, value);
        N++;
    }
}

© 著作权归作者所有

gaomq

gaomq

粉丝 5
博文 71
码字总数 26984
作品 0
合肥
程序员
私信 提问
查找----基于散列表(线性探测法)

上一篇:基于散列表(拉链法)的查找 参照数据结构--符号表API实现。 除了拉链法,实现散列表的另一种方式就是用大小为M的数组保存N个键值对。 线性探测法:当碰撞发生时,直接检测散列表中的...

Superheros
2017/12/16
31
0
哈希表知识点总结

一、基本原理: 假设我们使用一个下标范围比较大的数组来存储元素。设计一个函数(哈希函数,也叫做散列函数),使得每个元素的关键字经过函数运算得到一个函数值(即数组下标),于是用这个...

lindianlide
2014/09/02
0
0
Hashmap和HashTable

1. 关于HashMap的一些说法: HashMap实际上是一个“链表散列”的数据结构,即数组和链表的结合体。HashMap的底层结构是一个数组,数组中的每一项是一条链表。 HashMap的实例有俩个参数影响其...

就是小灰灰
2017/07/17
0
0
哈希相关知识再学习

在平时工作和源码学习的过程中经常遇到哈希相关的问题,每次都会上网找资料回忆哈希相关的知识点。趁这机会记录下来,防止以后又忘记了!! 哈希表 根据关键字(Key value)至二级访问在内存...

静默加载
2017/10/24
0
0
hash分布式算法及冲突解决方案

虽然我们不希望发生冲突,但实际上发生冲突的可能性仍是存在的。当关键字值域远大于哈希表的长度,而且事先并不知道关键字的具体取值时。冲突就难免会发 生。另外,当关键字的实际取值大于哈...

吴之恒心
2017/02/24
0
0

没有更多内容

加载失败,请刷新页面

加载更多

高速PCB设计软件allegro中与网络有关的约束规则设置

在allegro pcb的设计过程中,设计约束规则包括时序规则、间距规则、信号完整性规则以及物理规则等,本期主要详细讲解与物理、间距与电气约束中的线宽、线间距物理规则的设置。 一、线宽设置 ...

demyar
19分钟前
2
0
Linux 启动停止SpringBoot jar 程序部署Shell 脚本

#!/bin/bash #这里可替换为你自己的执行程序,其他代码无需更改 APP_NAME=algorithm.jar #使用说明,用来提示输入参数 usage() { echo "Usage: sh 执行脚本.sh [start|stop|restart|status]...

草庐过客
21分钟前
3
0
mysql-connector-java驱动升级到8.0后数据库保存时间出现时差

1.问题:在一个新项目中用到了新版的mysql jdbc 驱动后,发现保存到数据库的时间出现了时差 <dependency> <groupId>mysql</groupId> <artifactId>mysql-connector-java</artifactId>......

ValSong
23分钟前
3
0
好程序员大数据教程Scala系列之隐式转换和隐式参数

5.1. 概念 隐式转换和隐式参数是Scala中两个非常强大的功能,利用隐式转换和隐式参数,你可以提供优雅的类库,对类库的使用者隐匿掉那些枯燥乏味的细节。 5.2. 作用 隐式的对类的方法进行增强...

好程序员官网
27分钟前
3
0
多线程必备

初次接触线程,可能有很多初学者搞不明白,始终云里雾里,那么本篇文章直接带大家介绍多线程必须知道的几个点 接下来没有多余,直接上干货 1. 进程和线程的区别是什么? 进程是执行着的应用程序,...

理性思考
30分钟前
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部