精华内容
下载资源
问答
  • 主要介绍了java开放地址法和链地址法解决hash冲突的方法示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
  • hash表一般都采用取余构造(将一个数对n取余然后根据余数来查找是否存在该数),当两个数的余数相同时仅仅凭借余数作为下标来查找就会发生错误即hash冲突,那么链地址法其实就是将余数相同的数用链表储存起来,那么...
  • hash链地址法

    2018-08-28 17:01:30
    hash的链地址法,哈希表是一种根据关键码去寻找值的数据映射结构,该结构通过把关键码映射的位置去寻找存放值的地方
  • 链地址法处理Hash冲突

    2019-04-11 01:24:48
    NULL 博文链接:https://128kj.iteye.com/blog/1683641
  • 链地址法

    万次阅读 2019-05-03 16:04:14
    解决哈希表冲突的方法:开发地址法,链地址法 开发地址法:虽然解决了问题,但是1和101,1占据了一个数组,101只能向下,占据了2的数组,此时来一个取余为2 的值呢,只能向下继续寻找,同理,每一个来的值都只能向下...

    解决哈希表冲突的方法:开发地址法,链地址法

    开发地址法:虽然解决了问题,但是1和101,1占据了一个数组,101只能向下,占据了2的数组,此时来一个取余为2 的值呢,只能向下继续寻找,同理,每一个来的值都只能向下寻找,为了解决这个问题,引入了链地址法

    链地址法:在哈希表每一个单元中设置链表,某个数据项对的关键字还是像通常一样映射到哈希表的单元中,而数据项本身插入到单元的链表中。简单理解如下:

     来一个相同的数据,就将它插入到单元对应的链表中,在来一个相同的,继续给链表中插入。

    定义结点:


    /*
     * 链结点,相当于是车厢
     */
    public class Node {
        //数据域
        public Info info;
        //指针域
        public Node next;
        
        public Node(Info info) {
            this.info = info;
        }
        
    }

     

    初始化:


    /**
     * 员工信息类
     * @author Administrator
     *
     */
    public class Info {
        private String key;
        private String name;
        
        public Info(String key, String name) {
            this.key = key;
            this.name = name;
        }

        public String getKey() {
            return key;
        }

        public void setKey(String key) {
            this.key = key;
        }

        public String getName() {
            return name;
        }

        public void setName(String name) {
            this.name = name;
        }
        
        
    }

     

    定义链表:


    /*
     * 链表,相当于火车
     */
    public class LinkList {
        //头结点
        private Node first;
        
        public LinkList() {
            first = null;
        }
        
        /**
         * 插入一个结点,在头结点后进行插入
         */
        public void insertFirst(Info info) {
            Node node = new Node(info);
            node.next = first;
            first = node;
        }
        
        /**
         * 删除一个结点,在头结点后进行删除
         */
        public Node deleteFirst() {
            Node tmp = first;
            first = tmp.next;
            return tmp;
        }
        
        
        /**
         * 查找方法
         */
        public Node find(String key) {
            Node current = first;
            while(!key.equals(current.info.getKey())) {
                if(current.next == null) {
                    return null;
                }
                current = current.next;
            }
            return current;
        }
        
        /**
         * 删除方法,根据数据域来进行删除
         */
        public Node delete(String key) {
            Node current = first;
            Node previous = first;
            while(!key.equals(current.info.getKey())) {
                if(current.next == null) {
                    return null;
                }
                previous = current;
                current = current.next;
            }
            
            if(current == first) {
                first = first.next;
            } else {
                previous.next = current.next;
            }
            return current;
            
        }
    }

     

     定义方法:

     

    import java.math.BigInteger;

    public class HashTable {
        private LinkList[] arr;
        
        /**
         * 默认的构造方法
         */
        public HashTable() {
            arr = new LinkList[100];
        }
        
        /**
         * 指定数组初始化大小
         */
        public HashTable(int maxSize) {
            arr = new LinkList[maxSize];
        }
        
        /**
         * 插入数据
         */
        public void insert(Info info) {
            //获得关键字
            String key = info.getKey();
            //关键字所自定的哈希数
            int hashVal = hashCode(key);
            if(arr[hashVal] == null) {
                arr[hashVal] = new LinkList();
            }
            arr[hashVal].insertFirst(info);
        }
        
        /**
         * 查找数据
         */
        public Info find(String key) {
            int hashVal = hashCode(key);
            return arr[hashVal].find(key).info;
        }
        
        /**
         * 删除数据
         * @param key
         * @return
         */
        public Info delete(String key) {
            int hashVal = hashCode(key);
            return arr[hashVal].delete(key).info;
        }
        
        public int hashCode(String key) {
    //        int hashVal = 0;
    //        for(int i = key.length() - 1; i >= 0; i--) {
    //            int letter = key.charAt(i) - 96;
    //            hashVal += letter;
    //        }
    //        return hashVal;
            
            BigInteger hashVal = new BigInteger("0");
            BigInteger pow27 = new BigInteger("1");
            for(int i = key.length() - 1; i >= 0; i--) {
                int letter = key.charAt(i) - 96;
                BigInteger letterB = new BigInteger(String.valueOf(letter));
                hashVal = hashVal.add(letterB.multiply(pow27));
                pow27 = pow27.multiply(new BigInteger(String.valueOf(27)));
            }
            return hashVal.mod(new BigInteger(String.valueOf(arr.length))).intValue();
        }
    }

     

    进行测试:

     

    public class TestHashTable {
        public static void main(String[] args) {
            HashTable ht = new HashTable();
            ht.insert(new Info("a","张三"));
            ht.insert(new Info("ct","李四"));
            ht.insert(new Info("b","王五"));
            ht.insert(new Info("dt","赵柳"));
            
            System.out.println(ht.find("a").getName());
            System.out.println(ht.find("ct").getName());
            System.out.println(ht.find("b").getName());
            System.out.println(ht.find("dt").getName());
            
    //        System.out.println(ht.hashCode("a"));
    //        System.out.println(ht.hashCode("ct"));
            
            System.out.println(ht.delete("a").getName());
            System.out.println(ht.find("a").getName());

        }
    }

     

    展开全文
  • . c实现的哈希表。哈希函数采用除留余数法,处理哈希冲突采用链地址法。包含设计文档!在dev c++上验证过。. vs2010 中有代码.有修改过一些BUG.
  • 其实就是hashMap中使用较多的链地址法,也就是一开始我们图中展示的,基本结构仍然是一个数组,但是数组的每个单元维护的不再是一个个数据,而是一个个链表,也就是类似于linkedList这样的结构,当新插入的多个数据...

    hashMap对各位小伙们来说,没有不知道的了,使用过的人想必或多或少的都了解一点hashMap的底层实现原理,总结来说就是,数组+链表,至于源码的实现,大家可参看源码,今天想说的是hashMap是怎么解决hash冲突的呢?

    首先看一张图,
    在这里插入图片描述

    从这张图也大概可以看出来,hashMap维护的是一个数组,数组里面的每个单元又是一个个链表,那么为什么会产生hash冲突呢?这也就是接下来要探讨的问题。

    既是数组,必然会有长度,当我们在往数组中插入数据的时候,不管是什么类型的数据,对于数组来说,就是占据了某个下标对应的空间,那么当加入的数据越来越多的时候,是否会出现多个数据占据同一个位置呢?答案是肯定的,这就是hash冲突产生的原始因素;

    首先,我们先弄清楚几个概念,对于hashMap或者其他类似的map来说,我们往里面添加数据的时候,并不是直接往数组里面加,而是通过计算这个插入数据的hash值,即通过一个hash的算法,然后把这个值加进去,以后再去查找数据的时候,hashMap同样会根据你的key,倒推出这个hash值然后取出数据,即这个hash值可以理解为插入值对应的数组下表;

    但通过实验我们可以发现,hash函数计算不同的key的时候,可能得到相同的hash值,这样一来,如果再用这个hash值作为数组的标识这个值的下标,就无法定位这个值了,这个时候冲突就发生了;

    下面我们用代码来模拟一下这个使用开发地址法解决hash冲突的问题,首先定义一个对象,这里为Info,为了更接近真实场景,我们这里的属性都为字符串,

    什么是开放地址法呢?

    **

    当冲突发生的时候,通过查找数组的一个空位,将数据插入进去,而不再用hash函数计算获取数的下标,这个方法就叫做开发地址法;

    **

    public class Info {
    	private String key;			//关键字,或者能标识对象的唯一属性
    	private String name;		//值域
    	
    	public Info(String key, String name) {
    		this.key = key;
    		this.name = name;
    	}
    
    	public String getKey() {
    		return key;
    	}
    
    	public void setKey(String key) {
    		this.key = key;
    	}
    
    	public String getName() {
    		return name;
    	}
    
    	public void setName(String name) {
    		this.name = name;
    	}
    }
    

    接下来手工写一个hashTable,用于模拟hashMap,

    /**
     * 模拟hashMap
     *
     */
    public class HashTable {
    	
    	private Info[] arr;
    	
    	/**
    	 * 默认的构造方法
    	 */
    	public HashTable() {
    		arr = new Info[100];
    	}
    	
    	/**
    	 * 指定数组初始化大小
    	 */
    	public HashTable(int maxSize) {
    		arr = new Info[maxSize];
    	}
    	
    	/**
    	 * 插入数据
    	 */
    	public void insert(Info info) {
    		//获得关键字
    		String key = info.getKey();
    		//关键字所自定的哈希数
    		int hashVal = hashCode(key);
    		//如果这个索引已经被占用,而且里面是一个未被删除的数据
    		while(arr[hashVal] != null && arr[hashVal].getName() != null) {
    			//进行递加,避免漏找
    			++hashVal;
    			//循环
    			hashVal %= arr.length;
    		}
    		arr[hashVal] = info;
    	}
    	
    	/**
    	 * 查找数据
    	 */
    	public Info find(String key) {
    		int hashVal = hashCode(key);
    		while(arr[hashVal] != null) {
    			if(arr[hashVal].getKey().equals(key)) {
    				return arr[hashVal];
    			}
    			++hashVal;
    			hashVal %= arr.length;
    		}
    		return null;
    	}
    	
    	/**
    	 * 删除数据
    	 */
    	public Info delete(String key) {
    		int hashVal = hashCode(key);
    		//循环查找,数组中下标为hashVal的值,没有找到返回null
    		while(arr[hashVal] != null) {
    			if(arr[hashVal].getKey().equals(key)) {
    				Info tmp = arr[hashVal];
    				tmp.setName(null);
    				return tmp;
    			}
    			++hashVal;			//由于数组的值是连续的,为了避免漏找,需要依次往下找
    			hashVal %= arr.length;
    		}
    		return null;
    	}
    	
    	/**
    	 * 获得关键字的hash值,也可以自定义
    	 */
    	public int hashCode(String key) {
    		
    		BigInteger hashVal = new BigInteger("0");
    		BigInteger pow27 = new BigInteger("1");
    		for(int i = key.length() - 1; i >= 0; i--) {
    			int letter = key.charAt(i) - 96;
    			BigInteger letterB = new BigInteger(String.valueOf(letter));
    			hashVal = hashVal.add(letterB.multiply(pow27));
    			pow27 = pow27.multiply(new BigInteger(String.valueOf(27)));
    		}
    		return hashVal.mod(new BigInteger(String.valueOf(arr.length))).intValue();
    	}
    }
    

    可以看到,我们是通过对要插入的数值先进行hash编码,再对数值的长度进行取模i,这样得到的位置总能够落在数值的长度内,

    里面有个地方可能不太好理解,就是在插入数据的时候,我们使用while循环进行插入,既然是开发地址,也就是说数组的每一个闲置的空间我们都能使用,前提是这个位置没有被其他的值占用,由于数组是连续的,所以我们需要循环的去寻找一个这样的位置,所以才有 ++hashVal这段代码,直到找到了一个空位,然后我们把数据插入进去,

    在这里插入图片描述

    运行测试main方法,我们看到,数据成功插入,但通过hash函数计算得到的“a”和"ct"却是一样的,再一次印证了我们前面所说的问题,
    在这里插入图片描述

    以上便是所说的采用开发地址法解决hash冲突的解决方法,但这样就万无一失了吗?

    我们考虑一下,数据的长度是有限的,但我们可能会往数组里面添加很多数据进去,数组总有被填满的时候,那样开发地址法也不管用了,当然,实际业务中,如果可以预料数据的大小,我们可以采用这样的方式解决部分问题,但问题是这样确实不是万无一失的解决办法,

    更合适的方式是什么呢?其实就是hashMap中使用较多的链地址法,也就是一开始我们图中展示的,基本结构仍然是一个数组,但是数组的每个单元维护的不再是一个个数据,而是一个个链表,也就是类似于linkedList这样的结构,当新插入的多个数据通过计算hash函数得到的是相同的数组下标时候,我们只需要把值往这个索引位置维护的链表中插入即可,什么是链地址法呢?

    **

    在hash表每个单元中设置链表,某个要插入的数据项的关键字还是像通常那样映射到hash表的某个单元中,而数据项的本身则被插入到该单元维护的链表中;

    **

    下面用代码来实现一下这个过程,同上面所有不同的是,链表中的结构我们通过是维护者一个个节点,即Node ,对链表结构不熟悉的同学可以先自行百度一下,不是很难,

    1、定义一个对象Info,

    public class Info {
    	
    	private String key;
    	private String name;
    	
    	public Info(String key, String name) {
    		this.key = key;
    		this.name = name;
    	}
    
    	public String getKey() {
    		return key;
    	}
    
    	public void setKey(String key) {
    		this.key = key;
    	}
    
    	public String getName() {
    		return name;
    	}
    
    	public void setName(String name) {
    		this.name = name;
    	}
    	
    	
    	
    }
    

    2、定义一个Node作为链表中的基本存储单元,

    public class Node {
    
    	// 数据域
    	public Info info;
    	// 指针域,指向对下一个节点引用
    	public Node next;
    
    	public Node(Info info) {
    		this.info = info;
    	}
    
    }
    

    3、定义一个链表,

    /**
     * 模拟linkedList
     * 
     * @author asus
     *
     */
    public class LinkList {
    
    	// 头结点
    	private Node first;
    
    	public LinkList() {
    		first = null;
    	}
    
    	// 插入一个节点
    	public void insertFirst(Info info) {
    		Node node = new Node(info);
    		node.next = first;
    		first = node;
    	}
    
    	// 删除一个节点,在头结点后进行删除
    	public Node deleteFirst() {
    		Node temp = first;
    		first = temp.next;
    		return temp;
    	}
    
    	/**
    	 * 查找方法
    	 */
    	public Node find(String key) {
    		Node current = first;
    		while (!key.equals(current.info.getKey())) {
    			if (current.next == null) {
    				return null;
    			}
    			current = current.next;
    		}
    		return current;
    	}
    
    	/**
    	 * 删除方法
    	 */
    	public Node delete(String key) {
    		Node current = first;
    		Node previous = first;
    		while (!key.equals(current.info.getKey())) {
    			if (current.next == null) {
    				return null;
    			}
    			previous = current;
    			current = current.next;
    		}
    
    		if (current == first) {
    			first = first.next;
    		} else {
    			previous.next = current.next;
    		}
    		return current;
    
    	}
    
    }
    

    4、模拟hashMap的几个方法,

    public class HashTable {
    
    	private LinkList[] arr;
    
    	/**
    	 * 默认的构造方法
    	 */
    	public HashTable() {
    		arr = new LinkList[100];
    	}
    
    	/**
    	 * 指定数组初始化大小
    	 */
    	public HashTable(int maxSize) {
    		arr = new LinkList[maxSize];
    	}
    
    	/**
    	 * 插入数据
    	 */
    	public void insert(Info info) {
    		String key = info.getKey();
    		// 获取关键字的自定义hash函数
    		int hashVal = hashCode(key);
    
    		if (arr[hashVal] == null) {		//如果数组某个单元的位置为空,则需要重新构造一个linkList
    			arr[hashVal] = new LinkList();
    		}
    		arr[hashVal].insertFirst(info);
    	}
    
    	/**
    	 * 查找数据
    	 */
    	public Info find(String key) {
    		int hashVal = hashCode(key);
    		return arr[hashVal].find(key).info;
    	}
    	
    	/**
    	 * 删除数据
    	 */
    	public Info delete(String key){
    		int hashVal = hashCode(key);
    		return arr[hashVal].delete(key).info;
    	}
    	
    
    	/**
    	 * 自定义计算hash的函数
    	 */
    	public int hashCode(String key) {
    
    		BigInteger hashVal = new BigInteger("0");
    		BigInteger pow27 = new BigInteger("1");
    		for (int i = key.length() - 1; i >= 0; i--) {
    			int letter = key.charAt(i) - 96;
    			BigInteger letterB = new BigInteger(String.valueOf(letter));
    			hashVal = hashVal.add(letterB.multiply(pow27));
    			pow27 = pow27.multiply(new BigInteger(String.valueOf(27)));
    		}
    		return hashVal.mod(new BigInteger(String.valueOf(arr.length))).intValue();
    	}
    
    }
    

    和上面开发地址法插入数据和查找数据不同,此种方式进行数据查找的时候,其实是进行两次查到的,第一次定位数组中的位置,第二次去到链表中,调用链表的查找方法进行查找,这一点值得注意,插入和删除的思想也是类似,
    在这里插入图片描述

    下面我们来测试一下,可以看到,依然达到了效果,说明我们模拟的链地址法也生效了,
    在这里插入图片描述

    以上就是通过开发地址法和链地址法解决hash冲突的两种方式,希望对大家理解hashMap的底层原理有所帮助…感谢观看!

    展开全文
  • HASH地址冲突解决之链地址法

    千次阅读 2019-05-28 22:46:21
    原文地址《HASH地址冲突解决之链地址法》 1、什么是链地址法 在hash冲突产生时,将相同具有相同hash值的对象以链表的形式存储,更直白的表述就是数组中的每个元素不在是具体的每个要存储的对象了,每个元素代表具有...

    原文地址《HASH地址冲突解决之链地址法》
    1、什么是链地址法
    在hash冲突产生时,将相同具有相同hash值的对象以链表的形式存储,更直白的表述就是数组中的每个元素不在是具体的每个要存储的对象了,每个元素代表具有相同hash值对象组成的链表,通过对象内部的指针可以查询到下一个具有相同hash值的对象。 简单总结:将产生冲突的值以链表的形式连起来

    2、链地址法如何解决快速查询问题
    HashMap在解决存储对象存在hash冲突的问题时,采用的就是链地址法,将相同hash值的对象以链表的形式进行存储,当相同hash值对象过多即聊表过长时,hashMap在内存将链表转换成红黑树来加快对象的查询,这样做也会存在缺陷,就是在添加新元素时可能会产生二叉树的平衡操作。具体的相关实现源码在HashMap的方法中。

    3、链地址法处理hash冲突流程
    链地址法添加元素的大致流程图如下:

    添加元素时,通过对象的hash散列算法,获取当前对象的hash值,并找到当前元素在数组中存储的位置,如果当前位置的元素不为空,说明存在hash冲突,修改当前位置对象中的指针,使其指向当前待添加元素。这样具有相同hash值的对象在添加时只会不断的往列表中添加新元素。

    链地址法移除元素的操作流程如下:

    找到元素所在列表对应的数组下标,获取当前列表的头元素,通过对象的内部指针获取下一个元素,直至找到合适的元素并移除为止。整个操作并不需要对其他的数据进行地址的重新分配,相对于开放定址法而言,在添加或者移除元素时,操作都要更加方便简洁。但是由于对象中需要存储指向下一个对象的指针,在使用链地址法时所占用的空间要比开放定址法多。

    4、代码实例
    对象代码定义如下,内部包含一个指向下一个对象的引用。

    static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
    }
    添加新元素方法如下:

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }
    

    在代码中首先判断当前位置的元素是否为空,如果为空则根据参数新建一个node对象填充至当前位置,否则判断当前位置元素的next引用用是否为空,如果为空则
    根据参数新建一个node对象并将next引用指向当前新建的对象。如果引用也不为空那么会接着向下一个节点查询直至查询到next引用为空的对象为止,根据参数新建一个node对象并将next引用指向当前新建的对象

    移除指定元素的具体代码实现如下:

    final Node<K,V> removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) {
        Node<K,V>[] tab; Node<K,V> p; int n, index;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (p = tab[index = (n - 1) & hash]) != null) {
            Node<K,V> node = null, e; K k; V v;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                node = p;
            else if ((e = p.next) != null) {
                if (p instanceof TreeNode)
                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                else {
                    do {
                        if (e.hash == hash &&
                            ((k = e.key) == key ||
                             (key != null && key.equals(k)))) {
                            node = e;
                            break;
                        }
                        p = e;
                    } while ((e = e.next) != null);
                }
            }
            if (node != null && (!matchValue || (v = node.value) == value ||
                                 (value != null && value.equals(v)))) {
                if (node instanceof TreeNode)
                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                else if (node == p)
                    tab[index] = node.next;
                else
                    p.next = node.next;
                ++modCount;
                --size;
                afterNodeRemoval(node);
                return node;
            }
        }
        return null;
    }
    

    移除的操作主要分为两部分:

    查找到代移除的元素,在这里不仅需要判断key的hash值是否相同,还需要判断key是否相同,即是否为同一个对象。
    删除指定的对象,如果当前key在节点中存在下一个元素,需要修改key的上一个元素的next引用直接指向key的下一个元素。
    在解决hash冲突的时候,需要根据业务选择合适的方式来解决hash冲突带来的问题,如果存入的hash对象可以非常肯定不可能产生hash冲突的情况,建议还是使用开放定址法。如果无法判断,使用HashMap的实现方式来解决hash冲突不失为一种很好的选择。

    展开全文
  • 哈希表 用链地址法解决冲突:(哈希函数是按名字第一个大写字母分的) 输入内容:学生的姓名跟成绩 操作:插入、修改、查找、删除学生;以及输出哈希表
  • 所谓的开放定址就是一旦发生了冲突,就去寻找下一个空的散列地址,只要散列表足够大,空的散列地址总能找到,并将记录存入。 公式为: fi(key) = (f(key)+di) MOD m (di=1,2,3,......,m-1) 用开放定址解决冲突...

    试想一下,当你观望很久很久,终于看上一套房打算要买了,正准备下订金,人家告诉你,这房子已经被人买走了,你怎么办?对呀,再找别的房子呗!这其实就是一种处理冲突的方法开放定址法。

    开放定址法

    所谓的开放定址法就是一旦发生了冲突,就去寻找下一个空的散列地址,只要散列表足够大,空的散列地址总能找到,并将记录存入。

    线性探测法

    公式为:

    fi(key) = (f(key)+di) MOD m (di=1,2,3,......,m-1)
    

    用开放定址法解决冲突的做法是:当冲突发生时,使用某种探测技术在散列表中形成一个探测序列。沿此序列逐个单元地查找,直到找到给定的关键字,或者碰到一个开放的地址(即该地址单元为空)为止(若要插入,在探查到开放的地址,则可将待插入的新结点存人该地址单元)。查找时探测到开放的地址则表明表中无待查的关键字,即查找失败。
    探测方法

    比如说,我们的关键字集合为{12,67,56,16,25,37,22,29,15,47,48,34},表长为12。 我们用散列函数f(key) = key mod l2。

    当计算前S个数{12,67,56,16,25}时,都是没有冲突的散列地址,直接存入:
    开放地址法
    计算key = 37时,发现f(37) = 1,此时就与25所在的位置冲突。

    于是我们应用上面的公式f(37) = (f(37)+1) mod 12 = 2。于是将37存入下标为2的位置。这其实就是房子被人买了于是买下一间的作法:。开放地址法
    接下来22,29,15,47都没有冲突,正常的存入:在这里插入图片描述
    到了 key=48,我们计算得到f(48) = 0,与12所在的0位置冲突了,不要紧,我们f(48) = (f(48)+1) mod 12 = 1,此时又与25所在的位置冲突。于是f(48) = (f(48)+2) mod 12=2,还是冲突……一直到 f(48) = (f(48)+6) mod 12 = 6时,才有空位,机不可失,赶快存入:在这里插入图片描述
    我们把这种解决冲突的开放定址法称为线性探测法

    从这个例子我们也看到,我们在解决冲突的时候,还会碰到如48和37这种本来都不是同义词却需要争夺一个地址的情况,我们称这种现象为堆积。很显然,堆积的出现,使得我们需要不断处理冲突,无论是存入还是査找效率都会大大降低。

    二次探测法

    考虑深一步,如果发生这样的情况,当最后一个key=34,f(key)=10,与22所在的位置冲突,可是22后面没有空位置了,反而它的前面有一个空位置,尽管可以不断地求余数后得到结果,但效率很差。

    因此我们可以改进di = 12, -12, 22, -22,……, q2, -q2 (q <= m/2),这样就等于是可以双向寻找到可能的空位置。

    对于34来说,我们取di即可找到空位置了。另外增加平方运算的目的是为了不让关键字都聚集在 某一块区域。我们称这种方法为二次探测法。

    公式为:

    fi(key) = (f(key)+di) MOD m (di = 12, -12, 22, -22,……, q2, -q2, q <= m/2)
    

    随机探测法

    还有一种方法是,在冲突时,对于位移量 di 采用随机函数计算得到,我们称之为随机探测法。

    此时一定会有人问,既然是随机,那么查找的时候不也随机生成办吗?如何可以获得相同的地址呢?这是个问题。这里的随机其实是伪随机数。

    伪随机数是说,如果我们设置随机种子相同,则不断调用随机函数可以生成不会重复的数列,我们在査找时,用同样的随机种子,它每次得到的数列是相同的,相同的 di 当然可以得到相同的散列地址。

    公式为:

    fi(key) = (f(key)+di) MOD m (di是一个随机数列)
    

    总之,开放定址法只要在散列表未填满时,总是能找到不发生冲突的地址,是我们常用的解决冲突的办法。

    链地址法(拉链法)

    前面我们谈到了散列冲突处理的开放定址法,它的思路就是一旦发生了冲突,就去寻找下一个空的散列地址。那么,有冲突就非要换地方呢,我们直接就在原地处理行不行呢?

    可以的,于是我们就有了链地址法

    将所有关键字为同义词的记录存储在一个单链表中,我们称这种表为同义词子表,在散列表中只存储所有同义词子表的头指针

    对于关键字集合{12,67,56,16,25,37, 22,29,15,47,48,34},我们用前面同样的12为除数,进行除留余数法:
    在这里插入图片描述

    此时,已经不存在什么冲突换址的问题,无论有多少个冲突,都只是在当前位置给单链表增加结点的问题。很不错的解决思路吧?

    拉链法解决冲突的做法是:将所有关键字为同义词的结点链接在同一个单链表中。若选定的散列表长度为m,则可将散列表定义为一个由m个头指针组成的指针数组T[0…m-1]。凡是散列地址为i的结点,均插入到以T[i]为头指针的单链表中。T中各分量的初值均应为空指针。在拉链法中,装填因子α可以大于 1,但一般均取α≤1。

    拉链法的优势与缺点

    与开放定址法相比,拉链法有如下几个优点:

    • 1、拉链法处理冲突简单,且无堆积现象,即非同义词决不会发生冲突,因此平均查找长度较短;
    • 2、由于拉链法中各链表上的结点空间是动态申请的,故它更适合于造表前无法确定表长的情况;
    • 3、开放定址法为减少冲突,要求装填因子α较小,故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1,且结点较大时,拉链法中增加的指针域可忽略不计,因此节省空间;
    • 4、在用拉链法构造的散列表中,删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放地址法构造的散列表,删除结点不能简单地将被删结点的空间置为空,否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放地址法中,空地址单元(即开放地址)都是查找失败的条件。因此在用开放地址法处理冲突的散列表上执行删除操作,只能在被删结点上做删除标记,而不能真正删除结点。
    • 5、拉链法的缺点:指针需要额外的空间,故当结点规模较小时,开放定址法较为节省空间,而若将节省的指针空间用来扩大散列表的规模,可使装填因子变小,这又减少了开放定址法中的冲突,从而提高平均查找速度。

    链地址法的优势是对于可能会造成很多冲突的散列函数来说,提供了绝不会出现找不到地址的保障。当然,这也就带来了査找时需要遍历单链表的性能损耗,不过性能损耗在很多场合下也不是什么大问题。

    参考

    展开全文
  • 哈希表:线性探测法和链地址法求查找成功与不成功的平均查找
  • 什么是Hash冲突 由于Hash原理是将输入空间的值映射到Hash空间内,但Hash值的空间远远小于输入的空间。根据鸽巢原理,一定会存在不同输入被映射成相同输出的过程,这种情况...其中一种简单的表述为: 若有n个笼子...
  • 哈希表 哈希冲突解决之链地址法

    千次阅读 2020-02-24 16:30:42
    哈希函数: 使用特定的哈希...链地址法: 开放地址法中,通过在哈希表中寻找一个空位解决哈希冲突问题。另一个方法是在哈希表每个单元中设置链表。某个数据项的关键字还是像通常一样映射到哈希表的单元,而数据项本...
  • 1、链地址法 次日清晨,大臣们按时上朝,接着讨论昨日的话题。 “昨日Hash函数的选择我们已经有了具体的方案了,那就只剩下冲突的解决问题了”,王大臣率先发话。 “要解决冲突其实也不难,既然会有多个元素被Hash到...
  • 链地址法来解决冲突

    2020-07-06 21:51:04
    https://www.nowcoder.com/questionTerminal/858d5d6b72e24cf4b2ffc36aae04d433?orderByHotValue=0&pos=6&mutiTagIds=585
  • 哈希表-链地址法

    2017-12-20 13:50:39
    链地址法其实就是将实现哈希表的底层数组的类型变成链表,每次插入数据插入到链表中即可 package map; public class Node { private int data ; public Node next ; public Node ( int ...
  • 哈希表之链地址法

    2018-05-02 18:42:27
    链地址法比开放地址法要好。哈希化的效率:1,线性探测:成功查找P...不成功查找P=1/(1-L)3,链地址法:成功查找和插入P=1+L/2;不成功查找P=1+L比如装填因子L=1/2时,线性探测成功查找和不成功查找平均需要1.5次和2...
  • 哈希表 链地址法

    千次阅读 2019-03-28 16:37:25
    /*************************************************** 目的:将一堆整数存入hash...散列冲突方法:链地址法 ***************************************************/ #include <stdio.h> #include <stdlib...
  • 设散列表的长度为10,散列函数H(n)=n mod 7,初始关键字序列为 (33,24,8,17,21,10),用链地址法作为解决冲突的方法,平均查找长度是 1.5 33%7 = 5 24%7 = 3 //第一次出现3 8%7 = 1 17%7 = 3 //第二次出现3,...
  • 数据结构——拉链法(链地址法

    千次阅读 2019-12-10 20:54:16
    当存储结构是链表时,多采用拉链,用拉链处理冲突的办法是:把具有相同散列地址的关键字(同义词)值放在同一个单链表中,称为同义词链表。有m个散列地址就有m个链表,同时用指针数组T[0..m-1]存放各个链表的头...
  • 链地址法java代码

    2012-04-16 15:49:25
    链地址法java代码
  • 2.HashEntry 为哈希表所保存元素(即键值对 《key, value》)类型 3.HashTable 为哈希表,其中 bucket 指向大小为size的、元素类型为 4.HashEntry*的指针数组哈希表采用链地址法处理冲突 请实现 create_hash 函数,...
  • 哈希表(链地址法

    千次阅读 2018-10-26 11:31:57
    我前面说过哈希表的开放定址法,现在说说链地址法又称开散列法,在利用毕散列时我们说到有哈希冲突,而开散列法正好避开了哈希冲突,每个下标所在位置就是桶口,每个桶可以看做是一个链表,我们把哈希冲突的元素放在...
  • 数据结构 C语言 哈希 链地址法

    千次阅读 2017-07-05 11:01:20
    【问题描述】 为了美丽的校园计划,学校决定改进排队制度,比如说给饭卡充钱等…… 给每个人一个RP值,这个RP值决定这个人来了之后要排的位置,如果当前位置已经有人, ...任务要求:用链地址法解决冲突的方式建立
  • 1、链地址法中装填因子的定义 链地址法,又称分离链接法,是用于从处理散列函数构造冲突的一种办法。设散列函数得到的散列地址域在区间**[0,M-1]** ,关键字记录总数为N,则把链地址表中每个链表的平均长度定义为...
  • 采用链地址法处理冲突构造哈希表

    千次阅读 2018-01-25 23:00:28
    printf("-----------------------------------------------\n请选择要进行的操作:\n1、打印采用链地址法得到的哈希表\n"); printf("2、进行关键字查找\n3、退出\n----------------------------------------------...
  • 哈希表处理。。。用链地址法处理。。。建立关键字的头指针,然后依次插入。。。
  • 链地址法处理冲突 哈希表(链地址法处理冲突) 1000(ms) 10000(kb) 2681 / 6927 采用除留余数法(H(key)=key %n)建立长度为n的哈希表,处理冲突用链地址法。建立链表的时候采用尾插法。 输入 第一行为哈西表的...
  • 散列表(线性探测与链地址法

    千次阅读 2019-06-03 17:28:38
    以关键字除留余数法构建哈希函数H(key)=key MOD p,分别用线性探测再散列LinearConflict()和链地址法LinkConflict()处理冲突的方式来构建哈希表并计算其平均查找长度ASL,其中数据记录的数量n、哈希表的表长m>...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 153,069
精华内容 61,227
关键字:

链地址法