精华内容
下载资源
问答
  • 一、栈、队列、双端队列、优先队列本质栈的本质是以后进先出LIFO方式插入删除元素的数据结构队列的本质是以先进先出方式插入删除元素的数据结构双端队列的本质是栈+队列,同时支持先进先出和后进先出优先队列的本质...

    57cb9cadc627b14e19a1e49bbfe1e33a.png

    一、栈、队列、双端队列、优先队列本质

    • 栈的本质是以后进先出LIFO方式插入删除元素的数据结构
    • 队列的本质是以先进先出方式插入删除元素的数据结构
    • 双端队列的本质是栈+队列,同时支持先进先出和后进先出
    • 优先队列的本质是入队与队列相同,出队按优先级顺序出队,底层实现可能是堆、平衡二叉树等
    • 栈、队列、双端队列的的插入删除时间复杂度都是O(1),搜索和遍历时间复杂度都是O(n)
    • 优先队列的插入时间复杂度是O(1),取出的时间复杂度是O(logn)

    二、哈希表、映射、集合本质

    • 哈希表的本质是根据Key直接访问Value的数据结构,通过把Key经过Hash Function映射到表中某个位置,以加快访问速度
    • 映射的本质是key-value对,其中key唯一
    • 集合的本质是元素唯一
    • 哈希表的插入、删除、搜索时间复杂度都是O(1)

    三、Java Queue 和 Priority Queue源码分析

    • Priority Queue是通过数组实现一个堆,元素在queue数组中并不是完全有序的,仅堆顶元素最大或最小
    • poll方法,实际上是获取堆顶元素,然后调整堆
    • 调整堆的方法(大顶堆为例):
      1.判断是否传入comparator,有则按照comparator顺序,否则按照自然顺序排序
      2.取节点左右孩子节点的最大值,与父节点交换

    四、Java HashMap总结

    • 根据键的hashCode值存储数据,访问时间复杂度近似O(1),但遍历顺序不确定
    • 非线程安全,任意时刻可以有多个线程同时写HashMap,可能会导致数据混乱,如果需要满足线程安全,可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力,或者使用ConcurrentHashMap
    • 为了解决哈希冲突,Java采用链地址法(另一种方法是开放地址法),底层实现是数组+链表+红黑树的组合

    7ac2e5f9723d5644207d202edf37dd84.png
    Java 8 HashMap底层实现
    • 具体实现过程[1]为:
    1. 先调用key的hashCode方法得到hashCode值
    2. 再通过Hash算法中的高位运算和取模运算,确定键值对的存储位置
    3. 当HashCode值相等时,发生哈希碰撞,此时先判断当前地址下的的链表长度是否大于8,如果大于8就把链表转为红黑树,否则进行链表的插入操作
    4. 插入成功后,判断实际存在的键值对数量是否超过最大容量threshold,如果超过就扩容

    参考

    1. ^Java 8系列之重新认识HashMap https://tech.meituan.com/2016/06/24/java-hashmap.html
    展开全文
  • Java多线程编程是很考验一个程序猿水平的。传统的WEB程序中。由于框架提供了太多的健壮性、并发性、可靠性的支持,所以我们都是将全部的注意力放到了业务实现上。我们不过依照业务逻辑的要求。不停的积累自己的代码...

        Java多线程编程是很考验一个程序猿水平的。

    传统的WEB程序中。由于框架提供了太多的健壮性、并发性、可靠性的支持,所以我们都是将全部的注意力放到了业务实现上。我们不过依照业务逻辑的要求。不停的积累自己的代码。

    由于知识,或者是经验的限制。常常出现了问题而不自知。

    比如,某些比較原始的项目中。并没有使用Spring等相对来说比較灵活健壮的框架。

    而是只使用Servlet来作为服务端的实现方式。


        举一个简单的栗子。众所周知,当请求到了容器,容器是创建而且启动了一个Servlet线程来对当前的请求作出对应,这个时候。Servlet中的成员变量就会受到多线程的影响。这样,在Servlet中书写成员变量代码就会变得很的危急。由于毕竟不是一个线程安全的设计。多线程的同步、相互排斥、竞争、配合以及线程的中断等成了我们在编码过程中。很注意的一个知识点。


        Java核心技术中。说到怎样对多线程进行并发控制:首先:建议使用堵塞队列。堵塞队列是由专业的线程安全的一个数据结构。我们在这个上面进行编程,就如同站在巨人的肩膀上,至于非常多低层的实现就是他们去考虑的事情了。其次,假设想自己控制多线程并发的时候,尽可能的推荐使用synchronizedkeyword,synchronizedkeyword实际上就是等同于ReentrantLock或者读写锁的实现,只是语法更加简洁。更不太easy出错。FINALLY。最后,假设有充足的理由的时候,才会推荐使用ReentrantLock或者ReentrantReadWriteLock、ReadLock、WriteLock以及其对应的condition条、volatile等等,由于这些太过于低层,并且依照java一贯的实现编码逻辑,我们仅仅须要知道某一个控制线程并发数据结构的存在就能够了。


        以下是在核心技术上的一个非常好的。能够用来研究堵塞队列的Demo。目的是用于在某一个给定的目录以下。搜索全部含有某个keyword的文件,这中功能在非常多编辑器下都有详细的实现。比如UE。


        功能的实现方式大概是这种:生产者线程,将当前给定的目录以下的全部的文件,放到堵塞队列中(功能实现中使用了递归),最后,放置一个空的文件,作为一个标志。类似于一个信号灯的样子。创建了非常多的消费者线程,从堵塞队列中,循环获取一个文件,然后进行逐行遍历,假设其中含有keyword则打印。跳出循环的条件是看到了消费者线程放置的信号灯。功能的实现将并发依赖于一个并发的数据结构。非常值得去借鉴。

    import java.io.File;
    import java.io.FileInputStream;
    import java.io.IOException;
    import java.util.Scanner;
    import java.util.concurrent.ArrayBlockingQueue;
    import java.util.concurrent.BlockingQueue;
    
    
    public class BlockingQueueTest {
    	public static void main(String[] args) {
    		Scanner in = new Scanner(System.in);
    		System.out.println("Enter base directory(eg. /usr/local/jdk1.6.0/src)");
    		String directory = in.nextLine();
    		System.out.println("Enter keyword(e.g. volatile):");
    		String keyword = in.nextLine();
    		
    		final int FILE_QUEUE_SIZE=10;
    		final int SEARCH_THREADS =100;
    		
    		BlockingQueue<File> queue = new ArrayBlockingQueue<File>(FILE_QUEUE_SIZE);
    		
    		FileEnumerationTask enumerator = new FileEnumerationTask(queue,new File(directory));
    		new Thread(enumerator).start();
    		for(int i=1;i<=SEARCH_THREADS;i++){
    			new Thread(new SearchTask(queue,keyword)).start();
    		}
    	}
    }
    
    class FileEnumerationTask implements Runnable{
    
    	public FileEnumerationTask(BlockingQueue<File> queue,File startingDirectory){
    		this.queue=queue;
    		this.startingDirectory = startingDirectory;
    	}
    	@Override
    	public void run() {
    		try{
    			enumerate(startingDirectory);
    			queue.put(DUMMY);
    		}catch(InterruptedException e){
    		}
    	}
    	public void enumerate(File directory)throws InterruptedException{
    		File[] files = directory.listFiles();
    		for(File file : files){
    			if(file.isDirectory())enumerate(file);
    			else queue.put(file);
    		}
    	}
    	public static File DUMMY = new File("");
    	
    	private BlockingQueue<File> queue;
    	private File startingDirectory;
    }
    
    class SearchTask implements Runnable{
    	public SearchTask(BlockingQueue<File> queue,String keyword){
    		this.queue = queue;
    		this.keyword = keyword;
    	}
    	@Override
    	public void run() {
    		try {
    			boolean done = false;
    			while(!done){
    				File file = queue.take();
    				if(file==FileEnumerationTask.DUMMY){
    					queue.put(file);
    					done=true;
    				}
    				else {
    					search(file);
    				}
    			}
    		}catch(IOException e){
    			
    		} 
    		catch (InterruptedException e) {
    		}
    	}
    	
    	private void search(File file)throws IOException{
    		Scanner in = new Scanner(new FileInputStream(file));
    		int lineNumber = 0;
    		while(in.hasNextLine()){
    			lineNumber++;
    			String line = in.nextLine();
    			if(line.contains(keyword))System.out.printf("%s:%d:%s%n",file.getPath(),lineNumber,line);
    		}
    		in.close();
    	}
    
    	private BlockingQueue<File> queue;
    	private String keyword;
    }
    



    转载于:https://www.cnblogs.com/bhlsheji/p/5346880.html

    展开全文
  • Java多线程编程是非常考验一个程序员水平的。传统的WEB程序中,因为框架提供了太多的健壮性、并发性、可靠性的支持,所以我们都是将所有的注意力放到了业务实现上。我们只是按照业务逻辑的要求,不停的积累自己的...

        Java多线程编程是非常考验一个程序员水平的。传统的WEB程序中,因为框架提供了太多的健壮性、并发性、可靠性的支持,所以我们都是将所有的注意力放到了业务实现上。我们只是按照业务逻辑的要求,不停的积累自己的代码。因为知识,或者是经验的限制,经常出现了问题而不自知。例如,某些比较原始的项目中,并没有使用Spring等相对来说比较灵活健壮的框架。而是仅仅使用Servlet来作为服务端的实现方式。


        举一个简单的栗子,众所周知,当请求到了容器,容器是创建并且启动了一个Servlet线程来对当前的请求作出相应,这个时候,Servlet中的成员变量就会受到多线程的影响,这样,在Servlet中书写成员变量代码就会变得非常的危险,因为毕竟不是一个线程安全的设计。多线程的同步、互斥、竞争、配合以及线程的中断等成了我们在编码过程中,非常注意的一个知识点。


        Java核心技术中,说到如何对多线程进行并发控制:首先:建议使用阻塞队列,阻塞队列是由专业的线程安全的一个数据结构,我们在这个上面进行编程,就如同站在巨人的肩膀上,至于很多低层的实现就是他们去考虑的事情了。其次,如果想自己控制多线程并发的时候,尽可能的推荐使用synchronized关键字,synchronized关键字实际上就是等同于ReentrantLock或者读写锁的实现,不过语法更加简洁,更不太容易出错。FINALLY,最后,如果有充足的理由的时候,才会推荐使用ReentrantLock或者ReentrantReadWriteLock、ReadLock、WriteLock以及其相应的condition条、volatile等等,因为这些太过于低层,而且按照java一贯的实现编码逻辑,我们只需要知道某一个控制线程并发数据结构的存在就可以了。


        下面是在核心技术上的一个非常好的,可以用来研究阻塞队列的Demo,目的是用于在某一个给定的文件夹下面,搜索所有含有某个关键字的文件,这中功能在很多编辑器下都有具体的实现,例如UE。


        功能的实现方式大概是这样的:生产者线程,将当前给定的文件夹下面的所有的文件,放到阻塞队列中(功能实现中使用了递归),最后,放置一个空的文件,作为一个标志,类似于一个信号灯的样子。创建了非常多的消费者线程,从阻塞队列中,循环获取一个文件,然后进行逐行遍历,如果当中含有关键字则打印,跳出循环的条件是看到了消费者线程放置的信号灯。功能的实现将并发依赖于一个并发的数据结构,很值得去借鉴。

    import java.io.File;
    import java.io.FileInputStream;
    import java.io.IOException;
    import java.util.Scanner;
    import java.util.concurrent.ArrayBlockingQueue;
    import java.util.concurrent.BlockingQueue;
    
    
    public class BlockingQueueTest {
    	public static void main(String[] args) {
    		Scanner in = new Scanner(System.in);
    		System.out.println("Enter base directory(eg. /usr/local/jdk1.6.0/src)");
    		String directory = in.nextLine();
    		System.out.println("Enter keyword(e.g. volatile):");
    		String keyword = in.nextLine();
    		
    		final int FILE_QUEUE_SIZE=10;
    		final int SEARCH_THREADS =100;
    		
    		BlockingQueue<File> queue = new ArrayBlockingQueue<File>(FILE_QUEUE_SIZE);
    		
    		FileEnumerationTask enumerator = new FileEnumerationTask(queue,new File(directory));
    		new Thread(enumerator).start();
    		for(int i=1;i<=SEARCH_THREADS;i++){
    			new Thread(new SearchTask(queue,keyword)).start();
    		}
    	}
    }
    
    class FileEnumerationTask implements Runnable{
    
    	public FileEnumerationTask(BlockingQueue<File> queue,File startingDirectory){
    		this.queue=queue;
    		this.startingDirectory = startingDirectory;
    	}
    	@Override
    	public void run() {
    		try{
    			enumerate(startingDirectory);
    			queue.put(DUMMY);
    		}catch(InterruptedException e){
    		}
    	}
    	public void enumerate(File directory)throws InterruptedException{
    		File[] files = directory.listFiles();
    		for(File file : files){
    			if(file.isDirectory())enumerate(file);
    			else queue.put(file);
    		}
    	}
    	public static File DUMMY = new File("");
    	
    	private BlockingQueue<File> queue;
    	private File startingDirectory;
    }
    
    class SearchTask implements Runnable{
    	public SearchTask(BlockingQueue<File> queue,String keyword){
    		this.queue = queue;
    		this.keyword = keyword;
    	}
    	@Override
    	public void run() {
    		try {
    			boolean done = false;
    			while(!done){
    				File file = queue.take();
    				if(file==FileEnumerationTask.DUMMY){
    					queue.put(file);
    					done=true;
    				}
    				else {
    					search(file);
    				}
    			}
    		}catch(IOException e){
    			
    		} 
    		catch (InterruptedException e) {
    		}
    	}
    	
    	private void search(File file)throws IOException{
    		Scanner in = new Scanner(new FileInputStream(file));
    		int lineNumber = 0;
    		while(in.hasNextLine()){
    			lineNumber++;
    			String line = in.nextLine();
    			if(line.contains(keyword))System.out.printf("%s:%d:%s%n",file.getPath(),lineNumber,line);
    		}
    		in.close();
    	}
    
    	private BlockingQueue<File> queue;
    	private String keyword;
    }
    



    展开全文
  • 我需要一个数据结构,以支持最长时间前请求的项目的最有效的启动策略.例如,我有一堆不时要求的物品....如果再次添加“a”,我需要搜索整个队列来删除它.这是非常低效的,但我想不出任何有效的方法.也许是某种树形结构...

    我需要一个数据结构,以支持最长时间前请求的项目的最有效的启动策略.例如,我有一堆不时要求的物品.当我内存不足时,我想踢出我数据结构中最古老的项目(哈希映射).

    我在想像Queue这样的FIFO ds,但我不知道如何处理这种情况:

    –> a b c d a –>

    a是最古老和最新的项目.如果再次添加“a”,我需要搜索整个队列来删除它.这是非常低效的,但我想不出任何有效的方法.也许是某种树形结构,将最少访问的树结构保持在顶部?

    Java中是否有任何这种数据结构的实现?

    解决方法:

    LinkedHashMap是您追求的结构.从the docs开始:

    A special constructor is provided to create a linked hash map whose order of iteration is the order in which its entries were last accessed, from least-recently accessed to most-recently (access-order). This kind of map is well-suited to building LRU caches.

    Map map = new LinkedHashMap<>(CAPACITY, LOAD_FACTOR, true);

    boolean参数确定映射是访问顺序还是插入顺序. true表示访问顺序.

    此外,如果您希望地图作为LRU缓存工作,您可以创建自己的类来扩展LinkedHashMap并覆盖removeEldestEntry方法.再次,从文档:

    The removeEldestEntry(Map.Entry) method may be overridden to impose a policy for removing stale mappings automatically when new mappings are added to the map.

    这意味着您可以为缓存创建自己的类:

    public class Cache extends LinkedHashMap {

    private static final int MAX_ENTRIES = 100;

    public Cache() {

    super(SOME_INITIAL_CAPACITY, SOME_LOAD_FACTOR, true);

    }

    protected boolean removeEldestEntry(Entry entry) {

    return size() > MAX_ENTRIES;

    }

    }

    用法:

    Map map = new Cache<>();

    标签:java,data-structures

    来源: https://codeday.me/bug/20190827/1746084.html

    展开全文
  • 消息队列

    千次阅读 2010-12-30 10:14:00
    这是一个支持memcache协议的轻量级持久化服务器,因此使用php/perl/ruby/java等多种客户端都没问题,可以将较慢的处理逻辑通过消息队列放在后台处理,同时也支持多点分布式处理。   利用消息队列可以很好...
  • 广度优先搜索:bredth-first search BFS 图由节点和边组成。...队列支持两种操作:入队和出队 栈是一种后进先出(Last In First Out,LIFO)的数据结构 广度优先搜索运行时间为O(点数+边数),这通常写...
  • 1.新集合接口.(1)Deque:双端队列支持两端的插入和移出,扩展了Queue。(2)BlockingDeque:支持接下来操作的Deque,当读取一个元素时,等待Deque成为非空;当存储一个元素时,等待空间可用。扩展了Deque和...
  • Java集合

    2019-01-16 10:20:36
    Java Collections框架由接口和类组成,有助于处理不同类型的集合,如列表,集合,映射,堆栈和队列等。 这些即用型集合类解决了许多非常常见的问题,我们需要处理同类和异构对象组。涉及添加,删除,更新,排序,...
  • 推荐: 我花了半个月写的 2021 最新版 Java学习路线! (原创不易,欢迎点赞分享~) 推荐: 程序员需要达到什么水平才能顺利拿到 20k 无压力? (原创不易,欢迎点赞分享~) 推荐 在线阅读 (Github 访问速度比较慢可能会...
  • 推荐: 我花了半个月写的 2021 最新版 Java学习路线! (原创不易,欢迎点赞分享~) 推荐: 程序员需要达到什么水平才能顺利拿到 20k 无压力? (原创不易,欢迎点赞分享~) 推荐 在线阅读 (Github 访问速度比较慢可能会...
  • 阻塞队列提供了可阻塞的put和take方法,以及支持定时的offer和poll方法。这一结构非常适合用于实现生产者——消费者这种设计模式。 示例: 下面给出的例子实现一个给定路径的桌面搜索的功能(扫描给定路径上...
  • effective-java-3rd-chinese:Effective Java 中文版(第 3 版),Java 四大名著之一,本书一共包含 90 个条目,每个条目讨论 Java 程序设计中的一条规则。这些规则反映了最有经验的优秀程序员在实践中常用的一些...
  • JAVA FRAMEWORK

    千次阅读 2012-06-05 00:28:02
    1.新集合接口.(1)Deque:双端队列支持两端的插入和移出,扩展了Queue。(2)BlockingDeque:支持接下来操作的Deque,当读取一个元素时,等待Deque成为非空;当存储一个元素时,等待空间可用。扩展了Deque和...
  • java开源包1

    千次下载 热门讨论 2013-06-28 09:14:34
    6、支持多种通信框架(Mina/Netty/Grizzly),支持多种序列化/反序列化(Java/Hessian/PB); 7、支持自定义通信协议,可完全替换NFS-RPC自带的协议。 淘宝开放平台JAVA版SDK top4java 设计原则 容易维护扩展(不...
  • java开源包12

    热门讨论 2013-06-28 10:14:45
    6、支持多种通信框架(Mina/Netty/Grizzly),支持多种序列化/反序列化(Java/Hessian/PB); 7、支持自定义通信协议,可完全替换NFS-RPC自带的协议。 淘宝开放平台JAVA版SDK top4java 设计原则 容易维护扩展(不...
  • Java资源包01

    2016-08-31 09:16:25
    6、支持多种通信框架(Mina/Netty/Grizzly),支持多种序列化/反序列化(Java/Hessian/PB); 7、支持自定义通信协议,可完全替换NFS-RPC自带的协议。 淘宝开放平台JAVA版SDK top4java 设计原则 容易维护扩展(不...
  • java开源包101

    2016-07-13 10:11:08
    6、支持多种通信框架(Mina/Netty/Grizzly),支持多种序列化/反序列化(Java/Hessian/PB); 7、支持自定义通信协议,可完全替换NFS-RPC自带的协议。 淘宝开放平台JAVA版SDK top4java 设计原则 容易维护扩展(不...
  • java开源包11

    热门讨论 2013-06-28 10:10:38
    6、支持多种通信框架(Mina/Netty/Grizzly),支持多种序列化/反序列化(Java/Hessian/PB); 7、支持自定义通信协议,可完全替换NFS-RPC自带的协议。 淘宝开放平台JAVA版SDK top4java 设计原则 容易维护扩展(不...
  • java开源包2

    热门讨论 2013-06-28 09:17:39
    6、支持多种通信框架(Mina/Netty/Grizzly),支持多种序列化/反序列化(Java/Hessian/PB); 7、支持自定义通信协议,可完全替换NFS-RPC自带的协议。 淘宝开放平台JAVA版SDK top4java 设计原则 容易维护扩展(不...
  • Dubbo 支持哪些序列化协议?说一下 Hessian 的数据结构?PB 知道吗?为什么 PB 的效率是最高的? Dubbo 负载均衡策略和集群容错策略都有哪些?动态代理策略呢? Dubbo 的 spi 思想是什么? 如何基于 Dubbo 进行服务...
  • java开源包3

    热门讨论 2013-06-28 09:20:52
    6、支持多种通信框架(Mina/Netty/Grizzly),支持多种序列化/反序列化(Java/Hessian/PB); 7、支持自定义通信协议,可完全替换NFS-RPC自带的协议。 淘宝开放平台JAVA版SDK top4java 设计原则 容易维护扩展(不...
  • java开源包6

    热门讨论 2013-06-28 09:48:32
    6、支持多种通信框架(Mina/Netty/Grizzly),支持多种序列化/反序列化(Java/Hessian/PB); 7、支持自定义通信协议,可完全替换NFS-RPC自带的协议。 淘宝开放平台JAVA版SDK top4java 设计原则 容易维护扩展(不...
  • java开源包5

    热门讨论 2013-06-28 09:38:46
    6、支持多种通信框架(Mina/Netty/Grizzly),支持多种序列化/反序列化(Java/Hessian/PB); 7、支持自定义通信协议,可完全替换NFS-RPC自带的协议。 淘宝开放平台JAVA版SDK top4java 设计原则 容易维护扩展(不...
  • java开源包10

    热门讨论 2013-06-28 10:06:40
    6、支持多种通信框架(Mina/Netty/Grizzly),支持多种序列化/反序列化(Java/Hessian/PB); 7、支持自定义通信协议,可完全替换NFS-RPC自带的协议。 淘宝开放平台JAVA版SDK top4java 设计原则 容易维护扩展(不...
  • java开源包4

    热门讨论 2013-06-28 09:26:54
    6、支持多种通信框架(Mina/Netty/Grizzly),支持多种序列化/反序列化(Java/Hessian/PB); 7、支持自定义通信协议,可完全替换NFS-RPC自带的协议。 淘宝开放平台JAVA版SDK top4java 设计原则 容易维护扩展(不...
  • java开源包8

    热门讨论 2013-06-28 09:55:26
    6、支持多种通信框架(Mina/Netty/Grizzly),支持多种序列化/反序列化(Java/Hessian/PB); 7、支持自定义通信协议,可完全替换NFS-RPC自带的协议。 淘宝开放平台JAVA版SDK top4java 设计原则 容易维护扩展(不...
  • java开源包9

    热门讨论 2013-06-28 09:58:55
    6、支持多种通信框架(Mina/Netty/Grizzly),支持多种序列化/反序列化(Java/Hessian/PB); 7、支持自定义通信协议,可完全替换NFS-RPC自带的协议。 淘宝开放平台JAVA版SDK top4java 设计原则 容易维护扩展(不...
  • java开源包7

    热门讨论 2013-06-28 09:52:16
    6、支持多种通信框架(Mina/Netty/Grizzly),支持多种序列化/反序列化(Java/Hessian/PB); 7、支持自定义通信协议,可完全替换NFS-RPC自带的协议。 淘宝开放平台JAVA版SDK top4java 设计原则 容易维护扩展(不...

空空如也

空空如也

1 2 3 4 5 ... 9
收藏数 180
精华内容 72
关键字:

java队列支持搜索

java 订阅