精华内容
下载资源
问答
  • 哈希排序算法

    千次阅读 2020-03-05 11:27:39
    哈希排序 遇到这样一道题,数据很大,如果将数字排序后再输出,得到的结果是TLE(超时),我们选择用哈希排序的方法,降低时间复杂度到O(n)O(n)O(n),同时也牺牲了空间【用空间换取时间】。 将数的大小映射到数组...

    哈希排序
    遇到这样一道题,数据很大,如果将数字排序后再输出,得到的结果是TLE(超时)时间复杂度 O ( n 2 ) . O(n^2). O(n2).
    我们选择用哈希排序的方法,降低时间复杂度到 O ( n ) O(n) O(n),同时也牺牲了空间【用空间换取时间】。
    将数的大小映射到数组下标,下标越大,这个数越大,处理数组的数据实现。具体的数有多大,这个数组的范围就要开到多大,所以一定要仔细审题,理清题意中的范围。
    细节见代码注释…
    题目描述
    在这里插入图片描述
    T i m e L i m i t : 1000 m s Time Limit : 1000ms TimeLimit:1000ms

    #include<bits/stdc++.h>
    #define N 1000000
    using namespace std;
    int h[N];//N很大,声明全局数组
    //哈希算法,将数的大小映射到数组下标,下标越大,这个数越大,处理数组的数据实现
    int main() {
        int n,m,x;
        //int T;
        //cin>>T;
        while(scanf("%d%d",&n,&m)==2){//以EOF文件结束符结束
            //cin>>n>>m;
            int i,j;
            memset(h,0,sizeof(h));//循环内清零
            for(i=0;i<n;i++){
                cin>>x;
                h[x+N/2]++;//把-500000~500000映射到0~1000000并作为数组下标
            }
            int t=0;//用来计数,只输出m个
            for(i=N-1;i>=0;i--){
                for(j=0;j<h[i];j++){//相同的数输出h[i]次
                    cout<<i-N/2<<" ";
                    t++;
                    if(t==m) break;//退到上一层循环
                }
                if(t==m) break;//再退一次哦
            }
            cout<<endl;
        }
    } 
    
    
    展开全文
  • java哈希排序

    2016-12-27 17:00:02
    算法分析: 平均时间复杂度:希尔排序的时间复杂度和其增量序列有关系,这涉及到数学上尚未解决的难题;不过在某些序列。 中复杂度可以为O(n1.3)。 空间复杂度:O(1) 。 稳定性:不稳定。 ...
    代码实现:
       
    public class Insertion {
        @SuppressWarnings({ "rawtypes", "unchecked" })
        private static boolean less(Comparable v, Comparable m){
            return v.compareTo(m) < 0;
        }
        @SuppressWarnings({ "unused", "rawtypes" })
        private static void exch(Comparable [] a, int i, int j){
            Comparable t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
        @SuppressWarnings({ "unused", "rawtypes" })
        private static void show(Comparable [] a){
            System.out.println("排序之后:");
            for (int i = 0; i < a.length; i++) {
                System.out.print(a[i] + " ");
            }
        }
        @SuppressWarnings("rawtypes")
        public static boolean isSorted(Comparable [] a){
            //测试数组元素是否有序
            for (int i = 1; i < a.length; i++) 
                if (less(a[i], a[i-1])) 
                    return false;
            return true;
        }
        @SuppressWarnings("rawtypes")
        public static void sort(Comparable [] a){
            int N = a.length;
            int h = 1;
            while (< N/3)
                h = 3*+ 1;
            while (>= 1) {
                for (int i = h; i < N; i++) {
                    for (int j = i; j >= h && less(a[j], a[j-h]); j-=h) {
                        exch(a, j, j-h);
                    }
                }
                h = h/3;
            }
        }
        @SuppressWarnings("rawtypes")
        public static void main(String[] args) {
            //Comparable[] a = {49,38,65,97,76,13,27,49,78,34,12,64,1,8};
            Comparable[] a = {49,38};
            //String [] a = {"s","o","r","t","e","x","a","m","p","l","e"};
            System.out.println("排序之前:");
            for (int i = 0; i < a.length; i++) {
                System.out.print(a[i]+" ");
            }
            System.out.println();
            sort(a);
            assert isSorted(a);
            show(a);
        }
    }  
        
    排序之前:
    s o r t e x a m p l e 
    排序之后:
    a e e l m o p r s t x   
    算法分析:
    1. 平均时间复杂度:希尔排序的时间复杂度和其增量序列有关系,这涉及到数学上尚未解决的难题;不过在某些序列。
    2. 中复杂度可以为O(n1.3)。
    3. 空间复杂度:O(1)  。
    4. 稳定性:不稳定。
    展开全文
  • 五道大数据习题 1、海量日志数据,提取出某日访问百度次数最多的那个IP。 ①大文件 => 分解为小文件 hash(ip)%1000 1000个...③假设hash算法将同一个IP哈希到同一个文件 => 1000个在当前文件中频度最高的I...

    内容目录

    • 哈希结构概述
    • 代码实现
    • 注意问题
    • HashMap迭代的方式
    • 解决哈希冲突的方式
    • HashTable和HashMap的联系与区别
    • java中的四种引用
    • 五道大数据习题

    哈希结构概述
    1、概念:Hash(哈希),又称“散列”。哈希表综合数组和链表二者的特性,达到了查询容易,插入删除也容易的数据。
    ①数组 => 它在内存空间中是连续的,占用的内存比较多,我们添加删除一个元素的时候时间复杂度比较大,查询容易。
    ②链表 => 它在内存空间中是分散的,占用的内存也是分散的,添加删除一个元素的时候时间复杂度比较小,查询难。

    • hashCode() 表示的是对当前对象的唯一标示。计算 hashCode 的过程就称作哈希。
    • 最常用哈希表的数据结构:数组+链表 散列表。
    • 哈希表中存储键值对 key-value,散列指的是通过key定位到存储的位置,针对任意的key通过哈希算法转换为固定的位置(数组)。
    • key位置关系并不是一对一,多对一的关系,所以会引发哈希冲突。

    代码实现
    查找一个<key,value>为例
    1)先通过hash算法,找到与key对应的存储位置
    2)访问该位置的value与当前value比较,如果相等,直接返回
    3)反之才需要去当前链表中找

    class MyHash<K,V>{
    
        private Node<K,V>[] table;
    
        class Node<K, V>{
            protected K key;
            protected V value;
            protected Node<K, V> next;
        }
    
    }
    
    class MyPriorityQueue<E extends Comparable<E>>{
        private E[] queue;//存放元素的容器
        private int size; //有效元素个数
        private static int defaultCapacity = 5;
    
        public MyPriorityQueue(){
            this(defaultCapacity);
        }
    
        public MyPriorityQueue(int capacity){
            queue = (E[])new Comparable[capacity];
        }
    
        public void add(E val){
            //判满
            if(size == queue.length){
                //扩容
                queue = Arrays.copyOf(queue,queue.length*2);
            }
            if(size == 0){
                queue[0] = val;
                size++;
            } else{
                adjust(size, val);
                size++;
            }
    
        }
        public void adjust(int index,E val){
            while (index > 0) {
                int parentIndex = (index - 1) / 2;
                if (queue[parentIndex].compareTo(val) > 0) {
                    queue[index] = queue[parentIndex];
                    index = parentIndex;
                }else{
                    break;
                }
            }
            queue[index] = val;
        }
    
        public boolean remove(){
            //删除根节点元素
            //当前是一个空队列
            if (size == 0){
                return false;
            }
            int index = --size;
            //当前队列只有一个元素
            if (index == 0){
                queue[index] = null;
                return true;
            }
            queue[0] = null; //把根元素直接删除
            adjustDown(0, queue[index]);
            return true;
        }
    
        public void adjustDown(int index, E val){
            while (index < size/2) {
                int leftChild = index * 2 + 1;
                int rightChild = leftChild + 1;
                E minNode = null;
                int minIndex = 0;
                if (rightChild < size && queue[leftChild].compareTo(queue[rightChild]) >= 0) {
                    minNode = queue[rightChild];
                    minIndex = rightChild;
                } else {
                    minNode = queue[leftChild];
                    minIndex = leftChild;
                }
                if(val.compareTo(minNode) < 0){
                    break;
                }
                queue[index] = minNode;
                index = minIndex;
            }
            queue[index] = val;
        }
    
        public boolean remove(E val){
            int index = -1;
            for(int i=0; i<size; i++){
                if(val.equals(queue[i])){
                    index = i;
                    break;
                }
            }
    
            if(index == -1){
                return false;
            }
    
            if(size-1 == index){
                queue[--size] = null;
                return true;
            }else{
                //index - > size-1;
                queue[index] = queue[size-1];
                adjustDown(index, queue[index]);
                if(queue[index] == queue[size-1]){
                    adjust(index, queue[size-1]);
                }
                queue[--size] = null;
                return true;
            }
        }
    
        public String toString(){
            StringBuilder strs = new StringBuilder();
            for(int i=0; i<size; i++){
                strs.append(queue[i] +" ");
            }
            return strs.toString();
        }
    }
    

    主函数实现

        public static void main(String[] args) {
                Scanner input=new Scanner(System.in);
                int[]ten=new int[10];
                for(int a=1;a<10;a++){}
            MyPriorityQueue<Integer> my = new MyPriorityQueue<>();
            my.add(6);
            my.add(2);
            my.add(9);
            my.add(1);
            my.add(8);
            my.add(19);
            my.add(7);
            my.add(5);
            System.out.println(my.toString());
            my.remove();
            System.out.println(my.toString());
            my.remove(5);
            System.out.println(my.toString());
        }
    }
    

    注意问题
    1、 resize()的条件:
    1)table == null || table.length == 0
    2) size > threshold

    2、为什么不同的对象hashCode相同?
    hashCode实际指的某一个对象的内存地址,而返回的一个int类型,它是一个有限的集合,这就会导致哈希值和对象并不是一一对应的关系,所以不同对象来说hashCode有可能会相等

    HashMap迭代的方式

    HashMap<String, String> map = new HashMap<>();
    map.put("name", "zhangsna");
    map.put("age", "18");
    map.put("gender", "male");
    map.put("address", "shannxi");
    

    1、使用EntryIterator

    Iterator itr1 = map.entrySet().iterator();
    while(itr1.hasNext()){
    Map.Entry<String, String> entry = (Map.Entry<String, String>)itr1.next();
    System.out.println("key: " +entry.getKey() + " value: "+entry.getValue());
    }

    2、使用keyIterator

     Iterator itr2 = map.keySet().iterator();
        while(itr2.hasNext()){
            String key = (String)itr2.next();
            System.out.println("key: "+key+ " value: "+map.get(key));
        }
    

    3、使用valueIterator

     Iterator itr3 = map.values().iterator();
        while(itr3.hasNext()){
            String value = (String)itr3.next();
            System.out.println("value:"+value);
        }
    

    4、for each利用EntrySet遍历

    for(Map.Entry<String, String> entry:map.entrySet()){
            System.out.println("key: "+entry.getKey()+" value: "+entry.getValue());
        }
    

    5、jdk1.8 forEach进行遍历

    map.forEach((k,v)-> System.out.println("key: "+k+" value:"+v));
    

    解决哈希冲突的方式
    1、链地址法 key->hash->index->table[index] != null
    2、开放地址法 key->hash->index->table[index] != null
    冲突发生,顺序查看当前table,直到找到当前table下一个空的位置
    hash(key)+增量
    冲突发生,以2次幂的方式跳跃着去查找下一个为空的位置
    3、再哈希法
    4、公共溢出法

    HashTable和HashMap的联系与区别

    1、实现类、实现接口
    HashMap继承自AbstractMap,HashTable继承自Dictionnary
    实现接口都是Map、Cloneable、Serializable
    2、默认容量
    HashMap 16 HashTable 11
    3、构造函数
    HashMap在第一次put的时候初始化table
    HashTale构造函数中初始化table
    4、put方法
    ①HashMap ② HashTable
    ①是非同步方法 ②是同步方法
    ①key/value可为null ②key/value不能为null
    ①2倍方式扩容 ②2倍+1方式扩容(奇数)
    ①rehash ②table中从后往前去遍历,对每一个位置的每一个节点进行rehash,连接到新的位置
    ①该key不存在,尾插 ②头插

    java中的四种引用
    1、强引用 引用new创建出来的对象 GC永远都不会回收被引用的对象
    2、软引用 用来描述一些有用但是不需要永久使用的对象,可以使用软引用去关联对象,在系统内存不够用时,我们会将软引用对象回收,如果回收之后我们还没有足够的内存,那么会抛出一个内存溢出的异常 SoftReference

    用于Java对象的缓存
    3、弱引用 用来描述非必须的对象,但是比软引用更弱一些,被被弱引用关联的对象
    只能生存到下一次垃圾回收之前 WeakReference
    垃圾回收器是一个优先级低的线程,导致启动GC后,存在弱引用未被回收
    4、虚引用 最弱的引用,一个对象是否具有虚引用完全不会对其生存周期构成影响,因为我们无法通过虚引用去获得一个对象的实例 PhantomReference

    • WeakHashMap里面的健都是弱引用对象,当一个健对象被垃圾回收器回收时,那么相对应的值对象引用也会被从Map中删除。
    • 非必须对象,执行垃圾回收之后就会被删除掉。

    五道大数据习题
    1、海量日志数据,提取出某日访问百度次数最多的那个IP。
    ①大文件 => 分解为小文件 hash(ip)%1000 1000个小文件
    ②1000个小文件 => HashMap (IP,IP_count); => 当前HashMap根据IP_count进行排序
    ③假设hash算法将同一个IP哈希到同一个文件 => 1000个在当前文件中频度最高的IP
    ④将1000个IP进行排序即可

    2、有10个文件,每个文件1G,每个文件的每一行存放的都是用户的query,每个文件的query都可能重复。要求你按照query的频度排序。
    ①10个文件 => hash(query) => 10个小文件
    ②HashMap(query,query_count) => 当前HashMap根据query_count排序
    ③输出为10个有序的小文件
    ④归并排序

    3、有一个1G大小的一个文件,里面每一行是一个词,词的大小不超过16字节,内存限制大小是1M。返回频数最高的100个词。
    ①x hash(x)%2000 => 2000个文件,一个文件大概500K
    ②HashMap(x,x_count)
    ③首先第一文件中的频度最高100拿出来
    ④建小根堆
    ⑤依次遍历,如果当前文件频度最大的x > 此时小根堆的根元素
    ⑥替换调整

    4、10万个整数,找出重复的数字/找出第一个重复的数字。
    ①40 0000字节 => 400KB HashSet
    ②Boolean数组

    5、a,b两个文件,都存了50亿个IP地址,快速找出两个文件,有哪些IP是重复的。
    ①a,b => hash(IP)%5000,a0,…,a4999;b0,…,b4999;
    ②a0放到HashSet,判断b0中的元素在a0中是否存在
    ③以此类推

    展开全文
  • java排序算法java排序算法插入选择冒泡java排序算法插入选择冒泡
  • Hash排序(JAVA)

    千次阅读 2018-03-12 18:03:11
    什么是hash表:哈希表(Hash ... 哈希表的做法其实很简单,就是把key通过一个固定的算法函数即所谓的哈希函数转换成一个整型数字,然后就将该数字对数组长度进行取余,取余结果就当作数组的下标,将value存储在...

    什么是hash表:

    哈希表(Hash table,也叫散列表),是根据key而直接进行访问的数据结构。也就是说,它通过把key映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。

      哈希表的做法其实很简单,就是把key通过一个固定的算法函数即所谓的哈希函数转换成一个整型数字,然后就将该数字对数组长度进行取余,取余结果就当作数组的下标,将value存储在以该数字为下标的数组空间里。

        而当使用哈希表进行查询的时候,就是再次使用哈希函数将key转换为对应的数组下标,并定位到该空间获取value,如此一来,就可以充分利用到数组的定位性能进行数据定位


    展开全文
  •  本文分为三部分内容, 第一部分为一道百度面试题Top K算法的详解;第二部分为关于Hash表算法的详细阐述;第三部分为打造一个最快的Hash表算法;第四部分两个补充 感谢分享:...
  • 哈希(散列,Hash)算法总结-java

    千次阅读 2019-05-08 11:13:54
    目录 哈希算法简介 哈希算法的分类 加法Hash 位运算Hash ...除Hash ...常用的哈希算法 ...直接寻址 ...数字分析 ...折叠 ...随机数 ...哈希算法java中的使用 Object Integer Long String Ha...
  • 简介哈希函数整型浮点型字符串型Java 中的hashCode()实现 简介 实现哈希表有两个主要的问题, 一个是解决哈希函数的设计, 一个是哈希冲突的处理 哈希函数 键通过哈希函数可以得到一个索引, 通过索引可以在内存中找到...
  • Java世界里,HashMap是相当相当的重要,而和HashMap有关的哈希表是个什么东西? 百科解释: 散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键...
  • java,数据结构,蚀,算法,arraylist,队列,堆栈,树,图,哈希排序 代码01:代码测试,使用Eclipse IDE附加组件进行单元测试(使用JUnit)和覆盖率测试(使用EclEmma)。 代码02:BucketSort,Java接口简介,...
  • java哈希表及其应用详解

    万次阅读 多人点赞 2017-07-10 15:52:23
    什么是哈希表 数组和向量都可以存储对象,但对象的存储位置是随机的,也就是说对象本身与其存储位置之间没有必然的联系。当要查找一个对象时,只能以某种顺序(如顺序查找或二分查找)与各个元素进行比较,当数组或...
  • 分别是: 王王 Q仔 欧欧 Q妹 星星 Q妹 飞飞 Q妹 欣欣 Q妹 美美 Q仔 排序后 星星 Q妹 欣欣 Q妹 欧欧 Q妹 王王 Q仔 美美 Q仔 飞飞 Q妹 哈希算法 概述 根据设定的哈希函数H(key)和处理冲突的方法将一组关键字影像到...
  • [Java]Java哈希表之HashMap的常见用法和原理
  • Java的几种排序算法和查找算法

    千次阅读 2018-07-31 23:03:26
    一、介绍几种常见的排序算法:直接插入排序、简单选择排序、冒泡排序、快速排序。 1、直接插入排序 描述:在要排序的一组数中,假设前面(n-1)[n&gt;=2] 个数已经是排好顺序的, 现在要把第n个数插到前面的有序...
  • 希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的元素越来越多,当增量减至 1 时,整个待序列恰被分成一组,算法便终止,这时排序便已经完成。 希尔排序过程...
  • /* 哈希结点 */ class TheNode { int key; // 链表中的键 TheNode next; // 下一个节点 // public String toString() { return "TheNode [key=" + key + "]"; } } /* 在哈希表中查找关键字 */ public class...
  • public class SeqSearch { public static void main(String[] args) { int arr[] = { 1, 9, 11, -1, 34, 89 };// 没有顺序的数组 int index = seqSearch(arr, -11); if(index == -1) { ...
  • java简单实现一致性哈希算法

    千次阅读 2017-10-20 23:42:34
    什么是一致性哈希算法 一种特殊的哈希算法,这种算法使得哈希表、集群的规模在伸缩时尽可能减少重映射(remap)。 为什么需要它 一致性哈希基本解决了在P2P环境中最为关键的问题——如何在动态的网络拓扑(集群)中...
  • 主要介绍了Java语言Consistent Hash算法学习笔记(代码示例),分享了相关代码示例,小编觉得还是挺不错的,具有一定借鉴价值,需要的朋友可以参考下
  • 日历表格面板 [ConfigLine.java] 控制条类 [RoundBox.java] 限定选择控件 [MonthMaker.java] 月份表算法类 [Pallet.java] 调色板,统一配色类 Java扫雷源码 Java生成自定义控件源代码 2个目标文件 Java实现HTTP连接...
  • java数据结构算法

    千人学习 2019-11-22 10:12:46
    稀疏数组、单向队列、环形队列、单向链表、双向链表、环形链表、约瑟夫问题...哈希表、二叉树、二叉树与数组转换、二叉排序树(BST)、AVL树、线索二叉树、赫夫曼树、赫夫曼编码、多路查找树(B树B+树和B*树)、图、图的DFS...
  • Java知识体系最强总结(2021版)

    万次阅读 多人点赞 2019-12-18 10:09:56
    本人从事Java开发已多年,平时有记录问题解决方案和总结知识点的习惯,整理了一些有关Java的知识体系,这不是最终版,会不定期的更新。也算是记录自己在从事编程工作的成长足迹,通过博客可以促进博主与阅读者的共同...
  • 哈希表、Java中HashMap

    万次阅读 多人点赞 2016-08-05 01:24:46
    哈希算法,是一类算法哈希表(Hash Table)是一种数据结构; 哈希函数,是支撑哈希表的一类函数; Map是映射、地图的意思,在Java中Map表示一种把K映射到V的数据类型; HashMap是Java中用哈希数据结构实现的Map;...
  • Java_Data_Structures 广告: 仅在头部ptr排队,在头部删除旧的,在末尾附加新的 堆叠(顶推/弹出) 优先级队列(使用基于数组的二进制堆) 二进制堆操作: 遍历BFS 插入(使用heapifyUp确保堆属性) 删除...
  • 本文详细介绍了散列表的概念、散列函数的选择、散列冲突的解决办法,并且最后提供了一种散列表的Java代码实现。
  • 哈希树总结-java

    2019-04-19 15:42:36
    哈希树的java实现 节点 哈希哈希树的应用 哈希树的理论基础 质数分辨定律 这个定理可以简单的表述为:n个不同的质数可以“分辨”的连续整数的个数和他们的乘积相等。“分辨”就是指这些连续的整数不可能有...
  • java数据结构与算法-链地址法哈希

    千次阅读 2017-08-16 11:57:58
    一、链地址法哈希表代码如下: package com.tool.wpn.quicksort; import android.util.Log; /** * Created by Xi on 2017/8/16. * 链地址式哈希表 */ public class HashTablelink { private final String ...
  • 为什么Java String哈希乘数为31?

    千次阅读 2018-07-15 16:55:41
    前面简单介绍了[ 经典的Times 33 哈希算法 ],这篇我们通过分析Java 1.8 String类的哈希算法,继续聊聊对乘数的选择。 String类的hashCode()源码 /** Cache the hash code for the strin...
  • 1,对于待存储的海量数据,如何将它们分配到各个机器中去?---数据分片与路由 当数据量很大时,通过改善单机硬件资源的纵向扩充...这里主要记录一致性Hash算法如何将数据分配到各个机器中去。   2,衡量一致性哈

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 55,106
精华内容 22,042
关键字:

java哈希排序算法

java 订阅