精华内容
下载资源
问答
  • 数据结构——哈希表

    2021-10-02 13:11:15
    数据结构——哈希表 刀刀 第一次结束哈希表是在数据结构课上,在讲查找的时候老师随便提了一下哈希表这个概念,最近在做聊天室的时候要用到哈希表,更加深入的理解了哈希表。 1.什么是HashMap? 先说说存储结构,...

    数据结构——哈希表

    刀刀

    第一次结束哈希表是在数据结构课上,在讲查找的时候老师随便提了一下哈希表这个概念,最近在做聊天室的时候要用到哈希表,更加深入的理解了哈希表。


    1.什么是HashMap?

    先说说存储结构,实际上在我们学过的数据结构可以归结为两类:连续的的存储结构和不联系的存储结构,其代表分别为数组和链表。而我们学过的堆栈,队列,树,图,都可以用这两种结构来实现。连续的存储结构——数组,在数据的查找和修改上具有很好的优点,很方便,时间复杂度很小。但是在数据的增添和删除上则显得很麻烦,空间复杂度很大。而非连续,非顺序的存储结构——链表恰和数组相反,数据的增添和删除容易,空间复杂度很小,查找和修改复杂,时间复杂度很大。

    那么有没有一种数据结构能折衷一下数组和链表的优缺点呢?那就是——哈希表,既满足了数据的查找和修改很容易,同时又不占用很多空间的特点。

    哈希表是基于哈希函数的,哈希表中的元素是有哈希函数确定的,哈希表作为一种数据结构,我们用哈希表来存储数据,在保存的时候存入的是一个<key—value>的结构,value由哈希函数作用于key上得到。但是存在一个哈希冲突问题,那就是当你用hash函数作用在两个互不相同的key上,得到的value值相等。这就好比“一个班里面有两个叫做李洋的同学,老师上课的时候叫到李洋起来回答问题,这时就不知道是哪个李洋起来回答问题。”

    因此在创建一个哈希表的时候要考虑两个方面的问题:

    一. 构造一个好的哈希函数:所谓一个好的哈希函数指的就是,当用这个hash函数作用在不同的key时,所得到的value能够均匀的分布在hash表中,即能尽可能少的减少hash冲突。比较常见的hash函数的构造方法有:

    • 直接定址法
    • 数字分析法
    • 平方取中法
    • 折叠法
    • 除留余数法
    • 随机数法

    这里就不再对这些方法一一阐述。

    二. .hash冲突是不可能完全避免的,那么我们要考虑的还有就是当产生哈希冲突的时候,我们如何来解决。比较常见的hash冲突的解决方法有:

    • 开放定址法
    • 链地址法
    • 再哈希法

    2.为什么要用HashMap?

    首先,我们采用哈希表的初衷就是对连续的存储结构数组和非连续的存储结构链表,在数据的增删查改等操作上进行折衷。

    我们不妨设想一下有这样的一个场景:

    我们要设计一个数据表来保存用户信息,如果我们对用户信息有一个大致的估算为五万个,如果我们采用数组来保存的话,我们设计一个可以保存六万个用户的数组来作为数据表。我们在前面已经分析过了,如果用数组来保存,在数据的查询和修改方面相当方便,但是随着客户的增长,如果有一天客户增长到了五万零一个呢???这个时候我们就要建一个更大的数组来进行数据得迁徙。那如果用链表来进行存储呢?链表存储的话,在对用户的信息进行查询时,我们得从链表的第一个节点往后一个一个找,这个也是耗时耗力的。

    所以这个地方我有一种思路,那就是用链地址这种哈希构造方法来创建一个哈希表。在数据的增删查改方法上可以做到相对的要好。

    链地址法

    我们可以发现上面这个由“链地址法”构造的哈希表是由数组+链表构成的。元素的存入方法可以这样简单的来描述:

    首先我们创建一个容量为n的数组,让要存入的数据x对n取模,那么结果就存入对应的数组的下标中,当有一个元素要存入数组时,这个位置已经有一个元素了,那么我们就把这些哈希值相同的元素挂在已有的元素的后面生成一条链表。这就是对链地址法的哈希表的简单的描述。

    OK,我们简单的介绍到这里,下面我们会介绍一下JDK中的HashMap,和自己来写一个我的HashMap,并在数据存储的效率方面进行一下比对。


    3.实现我的HashMap

    /*
     * Entry类,相当于定义了链表一个节点的结构。
     */
    
    public class Entry<K, V> {
    	Entry<K, V> next;  
    	K key;
    	V value;
    	int hash;
    
    	public Entry(K k, V v, int hash) {
    		this.key = k;
    		this.value = v;
    		this.hash = hash;
    	}
    
    }

    每个Entry对象包括key(键),value(值),next(Entry的引用,可以形成单链表,用于解决哈希冲突)以及hash(哈希值)。

    /**
     * 哈希表的实现
     * 
     * @author ZhanHaoxin
     *
     */
    public class MyHashMap<K, V> {
    
    	private int size;// 当前容量
    	private static int initialCapacity = 16; // 默认初始容量为16
    	private static float loadFactor = 0.75f; // 默认装载因子为0.75
    	private Entry<K, V>[] container; // 存储数据的数据表
    	private int max; // 能存的最大数据量 等于装载因子和初始容量的乘积
    
    	/*
    	 * 使用默认参数的构造方法
    	 */
    	public MyHashMap() {
    		this(initialCapacity, loadFactor);
    	}
    
    	/*
    	 * 使用自定义参数的构造方法
    	 */
    	public MyHashMap(int Capacity, float factor) {
    		if (Capacity < 0) {
    			throw new IllegalArgumentException("容量有错:" + Capacity);
    		}
    
    		if (factor <= 0) {
    			throw new IllegalArgumentException("装载因子有错: " + factor);
    		}
    		this.loadFactor = factor;
    		max = (int) (loadFactor * Capacity);
    		container = new Entry[Capacity];
    		size = 0;
    	}
    
    	/*
    	 * 实现数据 存 的功能
    	 * 
    	 */
    	public boolean put(K k, V v) {
    		// 因为取模运算要求均为整数运算,这里key值不一定是整形,
    		//所以调用JDK的hashcode()方法
    		// 取得key的hash值用来进行取模运算
    		int hash = k.hashCode();
    		// 将参数信息封装为一个entry,entry即为哈希表中的“桶”中的元素
    		Entry<K, V> temp = new Entry(k, v, hash);
    		if (setEntry(temp, container)) { // 如果哈希表中无此值便插入
    			size++;
    			return true;
    		}
    		return false;
    	}
    
    	/*
    	 * 实现数据 取 的功能
    	 */
    
    	public V get(K k) {
    		Entry<K, V> entry = null;
    		// 计算K的hash值
    		int hash = k.hashCode();
    		// 根据hash值找到下标
    		int index = indexFor(hash, container.length);
    		// 根据index找到链表
    		entry = container[index];
    		// 若链表为空,返回null
    		if (null == entry) {
    			return null;
    		}
    		// 若不为空,遍历链表,比较k是否相等,如果k相等,则返回该value
    		while (null != entry) {
    			if (k == entry.key || entry.key.equals(k)) {
    				return entry.value;
    			}
    			entry = entry.next;
    		}
    		// 如果遍历完了不相等,则返回空
    
    		return null;
    	}
    
    	/*
    	 * 将指定的节点temp添加到哈希表中 添加时判断该结点是否已经存在 
    	 * 如果已经存在,返回false 添加成功返回true
    	 */
    	private boolean setEntry(Entry<K, V> temp, Entry<K, V>[] map) {
    		// 根据hash值找到下标
    		int index = indexFor(temp.hash, map.length);
    		// 找到下标位置对应的元素
    		Entry<K, V> entry = map[index];
    
    		if (null != entry) { // 若元素存在则遍历整个链表,判断值是否相等
    			while (null != entry) {
    				// 判断值是否相等除了要判断值相等还要判断地址是否相等
    				// 都相等的话就不存这个元素,返回false
    				if ((temp.key == entry.key || temp.key.equals(entry.key))
    					&& temp.hash == entry.hash
    			        && (temp.value == entry.value || temp.value.equals(entry.value))) 
    				{
    
    					return false;
    
    				} else if (temp.key == entry.key && temp.value != entry.value) {
    
    					entry.value = temp.value;
    					return true;
    				} else if (temp.key != entry.key) { // 不相等则往由链表往下比较
    
    					if (null == entry.next) {
    
    						break; // 到达链尾则跳出循环
    					}
    					entry = entry.next; // 没到链尾则继续下一个元素
    				}
    			}
    			// 此时遍历到了链尾还没相同的元素则把它挂在链尾
    			addEntry2Container(entry, temp);
    			return true;
    		}
    		// 若不存在,直接设置初始化元素
    		setFirstEntry(index, temp, map);
    		return true;
    	}
    	
         //桶中没有元素,把这个元素设为初始化元素
    	private void setFirstEntry(int index, Entry<K, V> temp, Entry<K, V>[] map) {
    		if (size > max) {
    			reSize(map.length * 2);
    		}
    		map[index] = temp;
    		temp.next = null;
    	}
    
    	//把hash值相同的元素挂在链表的尾部
    	private void addEntry2Container(Entry<K, V> temp, Entry<K, V> entry) {
    		if (size > max) {
    			reSize(container.length * 2);
    		}
    		entry.next = temp;
    
    	}
    
    	/*
    	 * 扩容的方法
    	 */
    
    	private void reSize(int newSize) {
    		// 创建一个新的数组
    		Entry<K, V>[] newMap = new Entry[newSize];
    		max = (int) (loadFactor * newSize);
    		// 将原来数组中的元素迁移到新数组中
    		for (int i = 0; i < container.length; i++) {
    			Entry<K, V> entry = container[i];
    			// 因为“桶”是链表,所以还要用next把桶中的元素连接起来
    			while (null != entry) {
    				setEntry(entry, newMap);
    				entry = entry.next;
    			}
    		}
    		container = newMap;
    	}
    
    	/*
    	 * 根据hashcode,容器数组长度,计算hashcode在容器数组中的下表值
    	 */
    	private int indexFor(int hashcode, int lengthOfContainer) {
    
    		return hashcode & (lengthOfContainer - 1);
    		// h & (length-1)就相当于h%length,用于计算index也就是在table数组中的下标
    	}
    
    }

    我实现的HashMap的数据结构

    其中table就是HashMap的核心,即为Entry数组,为数据结构图中绿色的部分;size 为HashMap中的Entry的数目,即数据结构中橙黄色部分的数目;loadFactor为加载因子,表示HashMap中元素的填满的程度。当加载因子大时,HashMap中的元素比较多,因而更容易产生哈希冲突;而当加载因子比较小时,HashMap中的元素比较少,会浪费空间。实时加载因子的计算方法为size/capacity,capacity即为 table数组的数目,均为2的n次幂。加载因子的默认值为0.75,即当实时加载因子到达0.75时,就会进行HashMap的扩容了。threshold表示当HashMap的size大于threshold时会执行哈希表的扩容即resize操作。 所以,其计算方法为 threshold = capacity * loadFactor。

    这里要说明的几个点:

    • 我们知道HashMap是由数组+链表组成,那么HashMap存在的两个极端就是HashMap可能退化为了一个数组或者是一个链表。
    • HashMap的resize是一个十分消耗资源的过程,在此基础上,就要求我们在哈希表的创建之初对数据的数量有一个良好的估计,还有就是rehash方法的优化。
    • Hash表的resize方法,在这里我们可以简单的理解为原有的桶不装不下这些数据了,还需要更多的桶,那么就是在hash函数中,我们还需要更大的模,产生更多的结果。

    HashMap方法操作的核心是找到key值所在的桶,然后便是按照单链表的操作进行查找、插入、删除或者其它操作了

    put 方法主要进行以下4个步骤

    1、判断key是否是null,是null的话单独处理,因为key为null总会将数据存储在第一个桶里;

    2、计算key的哈希值,并寻找到要存放该key的桶;

    3、判断桶内是否有该key,如果有的话,将老数据进行覆盖;

    4、将该key的相关数据添加到该桶里。

    get 方法要比 put 方法简单很多,主要流程为

    1、判断key是否是null,是null的话单独处理,因为key为null总会将数据存储在第一个桶里;

    2、计算key的哈希值,并寻找到要存放该key的桶;

    3、寻找桶内是否有该key的Entry,如果有,返回其value值,如果没有,返回null。

    在我的代码里只实现了哈希表的存和取的方法,其他的方法之后会更新,后面也会分析一下:

    • HashMap和HashTable的区别。
    • 一致性哈希。
    • JDK中HashMap源码解读

    4.我的HashMap和JDK中的HashMap在存取效率上的比较

    /**
     * 测试我的哈希表的存取速度
     *
     */
    public class testMyHashMap {
    
    	public static void main(String[] args) {
    
    		MyHashMap<String, String> testmap = new MyHashMap<String, String>();
    		long startTime = System.currentTimeMillis();
    		for (int i = 0; i < 100000; i++) {
    			testmap.put("user" + i, "password" + i);
    		}
    		long endTime = System.currentTimeMillis();
    		System.out.println("MyHashMap Insert Time:" + (endTime - startTime));
    
    		Long BeginTime = System.currentTimeMillis();// 记录BeginTime
    		testmap.get("user" + 9999);
    		Long EndTime = System.currentTimeMillis();// 记录EndTime
    		System.out.println("MyHashMap seach time:" + (EndTime - BeginTime));
    	}
    
    }
    

    结果为:

    /*
     * JDK中哈希表的存取速度
     */
    import java.util.HashMap;
    import java.util.Map;
    
    public class TestJDK {
    	public static void main(String[] args) {
    		HashMap<String, String> map = new HashMap<String, String>();
    		long startTime = System.currentTimeMillis();
    		for (int i = 0; i < 100000; i++) {
    			map.put("user" + i, "password" + i);
    		}
    		long endTime = System.currentTimeMillis();
    		System.out.println("JDK HashMap Insert Time:" + (endTime - startTime));
    		
    		
    		Long BeginTime = System.currentTimeMillis();// 记录BeginTime
    		map.get("user" + 9999);
    		Long EndTime = System.currentTimeMillis();// 记录EndTime
    		System.out.println("JDK HashMap seach time:" + (EndTime - BeginTime));
    	}
    
    }

    结果为:

    为什么我写的哈希表存入的速度比JDK的快呢???

    下次带你一起解读源码!!!

    展开全文
  • Java哈希表数据结构

    2021-03-14 14:48:54
    我们先将哈希表数据结构看成是这个样子: 那么整个map就是下图所示: 然后我们再来看put(key,value)和get(key)方法的实现原理。 map.put(key,value)实现原理: 第一步,先将key,value封装到Node对象中。 第二步,...

    我们先将哈希表数据结构看成是这个样子:
    在这里插入图片描述
    那么整个map就是下图所示:
    在这里插入图片描述

    然后我们再来看put(key,value)和get(key)方法的实现原理。

    map.put(key,value)实现原理:

    第一步,先将 key,value 封装到 Node 对象中。
    第二步,底层会调用k的hashCode()方法得出 hash 值。
    然后,通过哈希函数/哈希算法,将 hash 值转化为数组下标,下标的位置如果没有任何元素,就把 Node 添加到这个位置上了。如果说下标的位置上有链表,此时会拿着 key 和链表上的每一个节点中的 key 进行equals(),如果所有的equals()方法返回值都是false,那么新节点将被添加到链表的末尾。如果其中有一个equals()返回了true,那么这个节点的 value 将会被覆盖。

    v=map.get(key)实现原理

    先调用 key 的hashCode()方法得出哈希值,通过哈希算法转化成数组下标,通过数组下标快速定位到某个位置上(类似于查字典),如果这个位置什么也没有,返回 null 。如果这个位置上有单向链表,那么会拿着参数 key 和链表中的每个节点的 key 进行equals(),如果equals()方法返回false,那么 get 方法返回 null 。只要其中有一个节点的equals()方法返回了true,那么此时节点的 value 就是我们要找的值,get方法最终返回这个节点的 value 。

    为什么哈希表的随机增删,以及查询效率都比较高?

    增删是在链表上完成。
    查询不需要全部都扫描,只需要部分扫描。
    

    重点:通过讲解可以得出 hashMap 集合的 key ,会先后调用两个方法,一个方法是hashCode()方法,一个是equals()方法,那么这两个方法都要重写。

    HashMap部分特点

    无序不可重复
    为什么无序?因为不一定挂到哪个单向链表上
    不可重复是怎么保证的?equals方法来保证HashMap集合中的key不可重复
    如果key重复了,value会覆盖
    
    放在HashMap集合key部分的元素其实就是放到了HashSet集合中了
    所以HashSet集合中的元素也需要同时重写HashCode()和equals()方法
    

    哈希表使用不当时会无法发挥其性能!

    假设将所有的hashCode()方法的返回值固定为某个值,那么会导致哈希表变成纯单向链表。这种情况我们称为:散列分布不均匀。
    同理,假设将所有的hashCode()方法的返回值设定为都不一样的值,那么会导致哈希表变成一维数组,也是散列分布不均匀。

    HashMap的初始化容量为 16,默认加载因子是 0.75。
    这个默认加载因子是当HashMap集合底层数组的容量达到75%的时候,数组开始扩容。扩容之后是原容量 × 2
    这里提一下HashTable的初始容量是11,每次扩容是原容量 × 2+1

    重点记住HashMap集合初始化容量必须是2的倍数,这也是官方推荐的,这是因为达到散列均匀,为了提高HashMap集合的存取效率,所必须的。

    注意:JDK8后对HashMap进行了优化,当单向链表上的节点的个数超过8个时,链表会变成二叉树 / 红黑树。当节点个数小于6个时,二叉树会重新转换为单向链表。

    展开全文
  • 数据结构哈希表

    2021-11-10 09:33:24
    哈希表是一种数据结构,通过哈希函数来组织数据,以支持快速插入和搜索。 哈希表的关键思想是使用哈希函数将键映射到存储桶。更确切地说, 当我们插入一个新的键时,哈希函数将决定该键应该分配到哪个桶中,并将该...

    概念

    哈希表是一种数据结构,通过哈希函数来组织数据,以支持快速插入和搜索。

    哈希表的关键思想是使用哈希函数将键映射到存储桶。更确切地说,

    • 当我们插入一个新的键时,哈希函数将决定该键应该分配到哪个桶中,并将该键存储在相应的桶中;
    • 当我们想要搜索一个键时,哈希表将使用相同的哈希函数来查找对应的桶,并只在特定的桶中进行搜索。

    哈希冲突

    理想情况下,我们设计的哈希表可以将键和桶一一映射,然而很难实现。那要解决哈希冲突,我们可以将桶的结构设计成数组或者链表,如此就可以将冲突的键(或键值对)有组织地存储进来。

    哈希表的应用一:哈希集合

    哈希集合即将一个集合用哈希表的数据结构形式存放。

    下面是用数组方式创建的哈希集合:

    class MyHashSet:
    
        def __init__(self):
            self.size = 20
            self.buckets = [[] for i in range(self.size)] # 列表实现
    
        def hash(self, key):
            return key % self.size
    
        def add(self, key: int) -> None:
            index = self.hash(key)
            if not self.contains(key):
                self.buckets[index].append(key)
    
        def remove(self, key: int) -> None:
            index = self.hash(key)
            if self.contains(key):
                self.buckets[index].remove(key)
    
        def contains(self, key: int) -> bool:
            index = self.hash(key)
            if key in self.buckets[index]:
                return True
            else:
                return False
    
    
    # Your MyHashSet object will be instantiated and called as such:
    # obj = MyHashSet()
    # obj.add(key)
    # obj.remove(key)
    # param_3 = obj.contains(key)
    

    用数组方式存储桶里的数据,当对该桶里的数据进行插入或搜索时,和顺序表的复杂度一样,是O(N),而为了加快插入和搜索,我们可以将桶设计成链表。

    哈希表的应用二:哈希映射

    哈希映射和哈希集合类似,只不过桶里存储的是键值对。

    下面是数组方式创建的哈希映射:

    class MyHashMap:
    
        def __init__(self):
            self.size = 20
            self.buckets = [[] for i in range(self.size)]
    
        def hash(self, key):
            return key % self.size
    
        def put(self, key: int, value: int) -> None:
            index = self.hash(key)
            for item in self.buckets[index]:
                if item[0] == key:
                    item[1] = value
                    return
            tmp_list = [key, value]
            self.buckets[index].append(tmp_list)
    
        def get(self, key: int) -> int:
            index = self.hash(key)
            for item in self.buckets[index]:
                if item[0] == key:
                    return item[1]
            return -1
    
        def remove(self, key: int) -> None:
            index = self.hash(key)
            for item in self.buckets[index]:
                if item[0] == key:
                    self.buckets[index].remove(item)
    
    # Your MyHashMap object will be instantiated and called as such:
    # obj = MyHashMap()
    # obj.put(key,value)
    # param_2 = obj.get(key)
    # obj.remove(key)
    

    展开全文
  • 哈希表概念 决定一个哈希表的主要是哈希函数与处理冲突的方法。而按照设定的哈希函数和处理冲突的方法将一组关键字key 映射到有限的地址集合中,这就是哈希表。 哈希函数构造方法 直接定义法:代码块如下: int ...
    1. 哈希表概念
      决定一个哈希表的主要是哈希函数处理冲突的方法。而按照设定的哈希函数和处理冲突的方法将一组关键字key 映射到有限的地址集合中,这就是哈希表。可以根据处理冲突的方法不同,给哈希表不同的命名,如:链式哈希表,开放址哈希表。

    2. 哈希函数构造方法
      直接定义法:代码块如下:

    int hash1(int key){
    return a*key + b; //a 缩放, b 平移
    }
    

    除留取余法:(我接触最多的)
    区间长度为 m 的哈希表,取 不大于 m 的数 x 为模, H(key) = key % p。(理论上,p 取最接近 m 的素数最好了)

    int hash2(int key){
    return key % p;
    }
    

    数字分析法:了解不多,貌似没用到过。
    折叠法:
    移位折叠

    int  hash3(int key){
    itn i , j= 1, qu , sum = 0;
    for (i = 0; i < w; i++) 
    j * = 10;//按照w 位分割
    while (key != 0){
    qu = key % j;
    sum += qu;
    key /= j;
    }
    return sum;
    }
    

    平方取中法 :接触的很少(没有)

    1. 处理冲突
      当关键字key的数量大于哈希地址的元素个数时,就一定会产生冲突(几个不同的key 在同一个哈希地址)可以理解为一个关于x , y 的函数, x (key)不同时 , y (地址)是相同的 ,x1 != x2, 但是H(x1) = H(x2),这就是冲突。
      处理冲突的方法:
      链地址法:关键字为同一个地址的链接在同一个单链表中。
      开放地址法:
      Hi=(H(key)+di)% m ( i=1,2,…,n)
      1,线性探测:如果这个地址已经有元素了,就到下一个地址,直到找到空地址或者浏览完全表。
      di = 1,2,3……
      2,二次探测:左右跳跃的看
      di = 12,-12,22-22……
    2. 哈希表的实现
      1,开放地址哈希表(在论坛看了大佬的代码,然后自己思考写了一份,用的是线性探测)
    #include <stdio.h>
    #include <stdlib.h>
    //宏定义相关常量
    #define Max  10
    #define Size  10
    
    typedef struct Sqlist{
    int *data;
    int length;//长度
    }Sqlist;//顺序表
    
    typedef struct HashSqlist{
    int *data;
    int length;
    }HashSqlist;//哈希表
    
    int hash (int key){
    return key%10;
    }  //哈希函数
    
    void InitSqlist(Sqlist &l){ //这里l 还没定义,所以要加 &
    printf("Please int the length of the hashTable\n");
    scanf("%d",&l.length);
    l.data = (int *)malloc (Max * sizeof(int));
    printf("Please int %d numbers\n",l.length);
    for (int i = 0; i < l.length ; i ++)
    scanf("%d",&l.data[i]);
    }//建立一个顺序表,通过顺序表给哈希表赋值
    
    void InitHashSqlist(Sqlist l,HashSqlist &hl){
    hl.data = (int *)malloc (Max * sizeof (int ));
    hl.length = Size;
    int i,j,key;
    for (i = 0; i < hl.length; i ++)
    hl.data[i] = 0;
    for (i = 0; i < l.length ; i ++){
    key = hash(l.data[i]);
    if (hl.data [key]  != NULL){
    for (j = 1;  hl.data[key] != NULL; j ++)
    key = hash(l.data[i] + j);
    }
    hl.data[key] = l.data[i] ;
    printf("%d ----%d \n",key,hl.data[key]);//顺便输出,方便检验
    }
    }
    
    int main (){
    Sqlist l;
    HashSqlist hl;
    InitSqlist(l);
    InitHashSqlist(l,hl);
    return 0;
    }
    //目前只是初始化并且输出一个哈希表,有时间(学会后)再补上:查找、删除、替换等功能。
    
    	
    
    

    链式哈希表

    #include  <stdio.h>
    #include <stdlib.h>
    #define Max 10
    #define Size 10
    typedef struct Sqlist {
    int *data;
    int length;
    }Sqlist;
    
    typedef struct HashSqlist{
    int *data;
    int length;
    }HashSqlist;
    
    typedef struct Lnode{
    int data;
    struct Lnode * next;
    }Lnode,*HLinklist; //单链表
    
    typedef struct Hnode {
    Lnode *first;
    }Hnode,Hlist[Max];//定义一个指向链表第一个地址的哈希链表
    
    typedef struct HashTable{
    	 Hlist arr;//哈希表链地址 
    	int listNumber;//哈希地址个数 
    }HashTable;
    
    int hash(int key ){
    return key % 10;
    }
    
    void InitSqlist(Sqlist &l){
    printf("Please int the length of the hashTable\n");
    scanf("%d",&l.length);
    l.data = (int *)malloc (Max * sizeof(int ));
    printf("Please int %d numbers\n",l.length);
    for (int i = 0; i < l.length ; i ++)
    scanf("%d",&l.data[i] );
    }
    
    void InitHashTable(Sqlist l,HashTable &ht){
    Lnode *p,*q;
    ht.listNumber = l.length;
    int i , j , key;
    for (i  = 0; i < ht.listNumber; i ++)
    ht.arr[i].first = NULL;
    for(i = 0;i < l.length;i++){
    		p=(Lnode*)malloc(sizeof(Lnode));
    		p->data=l.data[i];
    		p->next=NULL;
    		key=hash(l.data[i]);
    		if (key > ht.listNumber)
    		ht.listNumber = key;
    		q=ht.arr[key].first;
    		if(q){
    			while(q->next){
    				q=q->next ;
    			}
    			q->next=p;
    		}
    		else
    			ht.arr[key].first=p;		
    	}
    	return;	
    } 
    
    void Output(HashTable ht){
    	int i;
    	HLinklist p,q;	
    	for(i=0;i<=ht.listNumber;i++){
    		p=ht.arr[i].first;
    		printf("%d----",i);
    		while(p){
    			printf("%d->",p->data);
    			p=p->next;	
    		}
    		printf("\n");
    	}
    	return ;
    }
    
    int main(){
     Sqlist l;
     HashTable ht;
     InitSqlist(l);
     InitHashTable(l,ht);// 链地址法解决冲突 
     Output(ht);
     return 0;	
    }
    //同样的,这个也只实现了初始化并且输出。学会后再更新。
    
    
    展开全文
  • 哈希函数 有一种函数,根据这个函数和查找关键字key,...哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快
  • 哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组...
  • 不同于往常的数据结构的是,往常的数据结构我们存储的数据比较单一,存储的标识比较简单,不能像数据库中的一条信息一样包含多个属性,为此,哈希表就可以简单实现这些要求 基本介绍 散列表(Hash table,也叫哈希...
  • python中的哈希表数据结构 散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做...
  • 哈希表、哈希值计算分析引出哈希表哈希表(Hash Table)哈希冲突(Hash Collision)JDK1.8的哈希冲突解决方案哈希函数如何生成 key 的哈希值Integer 的哈希值计算Float 的哈希值计算Long 的哈希值计算那么, `^` 和 ...
  • 数据结构与算法(哈希表) 哈希函数:在记录的关键字与记录的存储地址之间建立的一 种对应关系叫哈希函数。 哈希函数是一种映象,是从关键字空间到存储地址空间的一 种映象。可写成:addressi=H(keyi) ,其中i是表中...
  • 哈希表哈希表概念链式存储实现顺序存储实现实际应用字串匹配hash_table.htest.cpp 哈希表 概念 哈希表-散列表, 它是基于快速存储的角度设计的,也是一种典型的“空间换时间”的做法。 (键值(编号)就代表了这个数据...
  • 散列表(Hash table, 也叫哈希表) 是根据关键码值(Key value)而直接进行访问的数据结构。 也就是说, 它通过把关键码值映射到表中一个位置来访问记录, 以加快查找的速度。 这个映射函数叫做散列函数, 存放记录的...
  • java数据结构哈希表

    2021-03-17 16:09:30
    哈希表是根据关键码值(key-value)而直接进行访问的数据结构,它通过把关键码值映射到表的一个位置来访问记录,以加快查找的速度 直接来说数组就是一张哈希表 我们可以通过索引值对元素进行查找 常见的三种哈希...
  • 1.原理 字典是哈希键的底层实现,当一个哈希键包含的键值对比较多,或者键值对中元素都是比较长的字符串,Reids就会使用字典作为哈希键的底层实现 ... // 指向下一个哈希表节点 形成链表 }dictEntry; 字典节点也是
  • 哈希表 1.概念 哈希表是基于数组衍生出来的,哈希表高效的核心奥秘就是数组的随机访问能力~~ 结合我们之前所学的,我们知道在顺序结构以及平衡树中,元素关键码与其存储位置之间没有对应的关系,因此在查找一个元素...
  • 通过本实验的学习,理解哈希表的构造原理及构造方法,进一步理解通过哈希表的使用提高查找效率的原理,为不同数据结构选择合适的查找算法奠定基础。 二、实验内容 【问题描述】 针对你所在的班级中的“人名”设计一...
  • 哈希表的简单实现

    2021-01-27 09:25:25
    散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组 ...
  • 散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组...
  • 上次写的博客总结了数组实现哈希表,这次总结一下链表实现哈希表哈希表的基础知识在上次的数组实现哈希表里讲过了,这是链接:数组哈希 跳表结构如下: 那么我们来写它需要的结构体以及所需函数:先是数据类型的...
  • 哈希表:散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放...
  • C语言中, 标准库没有提供哈希表, 哈希表有多种实现方式,可参考以下实现—— 以下哈希表结构为 : 指定长度的哈希表长度,冲突的节点使用延展链表存储...2、哈希表数据节点的结构体 typedef struct tagHashNode { H
  • 哈希表是一种高效查找的数据结构,平均时空复杂度为O(1)。它的实现逻辑很简单:(eg.查找一个数x) 找一个数x 通过散列函数find()得出x应该在散列表h[]的存储位置 若h[find(x)] == x说明找到了,find(x)为存储位置 ...
  • 解决散列冲突文件结构字典类概念代码哈希类概念代码有序链表概念代码哈希表实现概念代码测试主函数代码输出 文件结构 字典类 概念 代码 //dictionary.h template<class K,class E> class dictionary { public:...
  • 数据结构中的哈希表

    2021-12-02 09:22:17
    哈希表是一种非常重要的数据结构,几乎所有的编程语言都有直接或间接的使用到这种数据结构。 介绍 哈希表通常是基于数组进行实现的,但是相对于数组,哈希表有许多的优势: 它可以提供非常快速的插入-删除-查找操作...
  • 哈希表实现

    2021-04-18 19:37:43
    哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组...
  • C语言哈希表的简单实现——数组+链表(拉链法) 1.哈希表简介 哈希表详细介绍可以参考这篇文章 2.哈希表拉链法实现 2.1完全由本人思路实现,如有错误,欢迎批评指正 哈希声明文件hash.h /* 哈希表 * by : I'M渣渣 * ...
  • 数据结构-哈希表

    千次阅读 2021-03-09 10:58:40
    文章目录一、什么是哈希表?1.1 认识哈希表1.2 案例一 公司员工存储1.3 案例二 联系人与电话存储1.4 案例三 50000个单词存储二、字母转数字的方案2.1 方案一2.2 方案二三、哈希表3.1 哈希化之后产生的 冲突3.2 深入 ...
  • 链地址法 链地址法是一种比较常见的解决冲突的方法(也称为拉链法) 链地址法解决冲突的办法是每个数组单元中存储的不再是单个数据,而是一个链条 这个链条通常使用数组或链表的数据结构 若为链表,也就是每个数组...
  • 1)数据结构 2)哈希函数 3)哈希链表初始化 4)哈希链表查找元素 5)哈希链表插入元素 6)哈希表删除元素 程序清单 定义 哈希表 - 散列表,它是基于快速存取的角度设计的,也是一种典型的“空间换时间”的...
  • 基于哈希表实现集合 class HashST1Set<Key> : ISet<Key> { private HashST1<Key> hashST1; public int Count { get { return hashST1.Count; } } public bool IsEmpty { get { return ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 185,734
精华内容 74,293
关键字:

哈希表数据结构实现

数据结构 订阅