Map 0f Java

整理关于Java的Map相关的知识,最近面试有被问到关于此类数据结构的知识,故写下来总结一番。List和Map都是java.util里面有关集合的数据结构类。Map主要的功能是元素对(键值对)的形式,每个键都映射到一个类。接下来我们介绍Map的分类、初始化、遍历的方式、排序方法以及常用API。Map类Java中的Map类可分为三种:通用Map:用于在应用程序内管理映射,通常在java.utils内HashMap、Hashtable、Properties、LinkedHashMap、IdentityHashMap、TreeMap、WeakHashMap、ConcurrentHashMap专用Map:不必我们自己创建,而是通过其他应用程序访问java.util.jar.Attribute、javax.print.attribute.standard.PrinterStateReasons、java.security.Provider、java.awt.RenderingHints、javax.swing.UIDefaults自定义Map常用类型的区别HashMap最常用的Map,速度快,非同步(不支持线程同步)允许一条键为null:多了覆盖允许多条值为nullTreeMap用Iterator遍历的时候返回以key为序的序列故不允许key为空非同步HashTable类似HashMap,但是写入速度慢因为支持线程同步:同一时刻只能有一线程能写HashTableLinkedHashMap保持了插入顺序,Iterator遍历时先进先出key、value都允许为空用法1234567891011//建立HashMap<String, String> map = new HashMap<String, String>();//寻值map.get("key1");//插入map.put("key2", "value2");//移除map.remove("key1");//清空map.clear();//Map的遍历初始化123Map<String, String> map = new HashMap<String, String>();map.put("key1", "value1");map.put("key2", "value2");分别使用增强for循环和Iterator来遍历增强for循环遍历KeySet遍历123for (String key: map.keySet()){ System.out.println(key + ": " + map.get(key));}entrySet遍历12for (Map.Entry<String, String> entry: map.entrySet()){ System.out.println(entry.getKey()…

0 Comments

Sort Algorithms of Linear Time Complexity

常用排序算法如归并、快排、堆排序等基于比较的排序方法都是不能突破$O(n log n)$时间复杂度的,本文着重介绍几种线性时间复杂度的排序方法。基于比较的排序为何不能突破$O(n log n)$时间复杂度?因为$N$个数有$N!$个可能的排列情况,也就是说基于比较的排序算法的判定树有$N!$个叶子结点,比较次数至少为$log(N!)= O(N log N)$ (斯特林公式)而线性复杂度的排序方法通常来说有计数排序、桶排序和基数排序三种。计数排序计数排序(Counting sort)是一种稳定的线性时间排序算法,Θ(n + k)的时间复杂度。n 是待排序数组的大小,k 是辅助数组 count 的大小。因为它并不是基于比较的的排序算法,所以它没有O(NlogN)的下限。并且在一定的条件下,使用该算法比使用快排能带来更好的效率。例如在基数排序中就运用了计数排序,因为它只需要额外的10个元素大小的辅助数组,线性的效率,并保证了稳定性。原理计数排序的主要思想是将待排序元素的值作为下标,利用辅助数组 count 记录所有的元素出现的次数。即 count[i] 的值代表元素 i 在原始数组中出现的次数。这样,原始数组的所有元素就被有有序地记录下来。当然,只知道某个元素出现的次数是不足以排序的。仔细观察 count 数组,发现对 count 数组进行累加(count[i] += count[i-1])后,count[i] 的含义就变成了原始数组 i…

0 Comments

Polymorphism of Java

最近面试被问到Java的多态怎么理解,自己含含糊糊的感觉自己知道点含义可是就是具体怎么说打不出来,尴尬死。接下来打算把三大特性:封装、继承、多态都好好的写下来,以参考。本文先写关于Java的多态吧。多态,用一句话来说,就是事物在运行过程中存在不同的状态。多态的存在有三个前提:要有继承关系子类要重写父类的方法父类引用指向子类对实验我们先定义一个父类Animal1234567891011121314151617class Animal{ int num = 10; int age = 20; public void eat(){ System.out.println("动物在吃饭"); } public stastic void sleep(){ System.out.println("动物在睡觉"); } public void run(){ System.out.println("动物在奔跑"); }}再定义一个子类Cat1234567891011121314151617class Cat extends Animal{ int…

0 Comments