java集合

JAVA集合

哪些集合类是线程安全的？

Vector、Hashtable、Stack 都是线程安全的，而像 HashMap 则是非线程安全的，不过在 jdk 1.5 之后随着 java.util.concurrent 并发包的出现，它们也有了自己对应的线程安全类，比如 HashMap 对应的线程安全类就是 ConcurrentHashMap。

list :LinkedList,ArrayList 和vector

LinkedList 接口实现类， 链表， 插入删除， 没有同步， 线程不安全
ArrayList 接口实现类， 数组， 随机访问， 没有同步， 线程不安全
Vector 接口实现类 数组， 同步， 线程安全

set：HashSet和TreeSet

HashSet 使用哈希表存储元素，元素可以是null
LinkedHashSet 链表维护元素的插入次序
TreeSet 底层实现为红黑树，元素排好序，元素不可以是null

map：HashMap、TreeMap和HashTable

线程安全

HshaMap线程不安全
TreeMap线程不安全
HashTable线程安全

空值

HashMap一个null key,多个null value
TreeMap不能null key，多个null value
HashTable都不能有null

继承和接口

HashMap继承AbstractMap，实现接口Map
TreeMap继承AbstractMap，实现接口NavigableMap(SortMap的一种)
HashTable继承Dictionary，实现接口Map

顺序

HashMap中key是无序的
TreeMap是有序的
HashTable是无序的

构造函数

HashMap有调优初始容量和负载因子
TreeMap没有
HashTable有

数据结构

HashMap是链表+数组+红黑树
TreeMap是红黑树
HashTable是链表+数组

list、set和map的区别

list：元素按进入先后有序保存，可重复
set：不可重复，并做内部排序
map:代表具有映射关系的集合，其所有的key是一个Set集合，即key无序且不能重复。

Collection：单列集合的根接口

Map：双列集合的根接口，用于存储具有键（key）、值（value）映射关系的元素。

List：元素有序 可重复

● ArrayList：类似一个长度可变的数组 。适合查询，不适合增删
● LinkedList：底层是双向循环链表。适合增删，不适合查询。

Set：元素无序，不可重复

● HashSet：根据对象的哈希值确定元素在集合中的位置
● TreeSet: 以二叉树的方式存储元素，实现了对集合中的元素排序

LinkedHashSet继承于HashSet、又基于 LinkedHashMap 来实现

TreeSet使用二叉树的原理对新 add()的对象按照指定的顺序排序（升序、降序），每增加一个对象都会进行排序，将对象插入的二叉树指定的位置。

HashSet存储元素的顺序并不是按照存入时的顺序（和 List 显然不同） 而是按照哈希值来存的所以取数据也是按照哈希值取得

Set集合的底层是如何保证数据的不重复？

在往Set集合中添加对象的时候，首先会通过该对象的hashCode方法计算该对象的hash值。

如果该对象的hash值不存在，表示集合中不存在新的对象，将元素存入set集合中，如果hash值已经存在，则进一步的比较值是否相等，调用equals方法进行比较，如果值不相等，说明不是同一个对象，会将这个对象添加到已有对象的末尾。

总结：

新插入元素后，计算元素的hash值，如果计算的hash值在hash字典表中不存在，则为新插入的元素，插入 Set集合中，但是如果数据的hash值已经存在，在进行equal进行值的比较，如果值相等，插入失败，否则将对象插入源对象的链表尾部。

ArrayList与LinkedList的区别

● arrayList使用的是数组数据结构，可以以O(1)时间复杂度对元素进行随机访问；LinkedList使用的是（双）链表结构查找某个元素的时间复杂度是O(n)
● arrayList更适合于随机查找操作，linkedList更适合增删改查，时间复杂度根据数据浮动
● 两者都实现了List接口，但LinkedList额外实现了Deque接口，因此Linked还可以当作队列使用
● LinkedList比ArrayList更占内存，因为LinkedList为每一个节点存储了两个引用，一个指向前一个元素，一个指向下一个元素

 //遍历ArrayList
    public static void main(String args[]){
        List<String> list = new ArrayList<String>();
        list.add("luojiahui");
        list.add("luojiafeng");

        //方法1
        Iterator it1 = list.iterator();
        while(it1.hasNext()){
            System.out.println(it1.next());
        }

        //方法2
        for(Iterator it2 = list.iterator();it2.hasNext();){
             System.out.println(it2.next());
        }

        //方法3
        for(String tmp:list){
            System.out.println(tmp);
        }

        //方法4
        for(int i = 0;i < list.size(); i ++){
            System.out.println(list.get(i));
        }

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

ArrayList和LinkedList有什么区别

ArrayList和LinkedList都实现了List接口，他们有以下的不通电
ArrayList是基于索引的数据接口，底层是数组，它可以以O(1)时间复杂度对元素进行随机访问。
对应的是LinkedList是以元素列表的形式存储它的数据，每一个元素都和它的前一个和后一个元素链接在一起，在这种情况下，

总结：
ArrayList基于数组，LinkedList基于链表

JAVA中的集合类

第一代线程安全集合类

Vector,Hashtable
是怎么保证线程安排的；使用synchronized修饰方法
缺点：效率低下

第二代线程非安全集合类

ArrayList ,HashMap
线程不安全，但是性能好，用来代替vector和Hashtable
使用ArrayList ，HashMap，需要线程安全怎么办呢？
使用Collections.synchronizedList(list);Collections.synchronizedMap(m);
底层使用synchronized代码块锁，虽然也是锁住了所有代码，

第三代线程安全集合类

在大量并发情况下如何提高集合的效率和安全呢

JAVA中的数据结构

Java哈希表

hashCode() 和equals()方法的重要性体现在上面地方？

Java中的HashMap使用hashCode()和equals()方法来确定键值对的索引，当根据键获取值的时候也会用到这两个方法。如果没有正确的实现这两个方法，两个不同的键可能会有相同的hash值，因此，可能会被集合认为是相等的。而且，这两个方法也用来发现重复元素。所以这两个方法的实现对HashMap的精确性和正确性是至关重要的。

请说一说,Java中的HashMap的工作原理是什么？

HashMap是以键值对的形式存储元素的，需要一个哈希函数，使用hashcode和eaquels方法，从集合中添加和检索元素，调用put方法时，会计算key 的哈希值，然后把键值对存在集合中合适的索引上，如果键key已经存在，value会被更新为新值。另外HashMap的初始容量是16，在jdk1.7的时候底层是基于数组和链表实现的，插入方式是头插法。jdk1.8的时候底层是基于数组和链表/红黑树实现的，插入方式为尾插法。

介绍一下，什么是hashmap?

HashMap 是一个散列表，它存储的内容是键值对(key-value)。
HashMap 继承于AbstractMap，实现了Map、Cloneable、java.io.Serializable接口。
HashMap 的实现不是同步的，所以它不是线程安全的。它的key、value都可以为null。此外，HashMap中的映射不是有序的。
HashMap 的实例有两个参数影响其性能：“初始容量” 和 “负载因子”。容量 是哈希表中桶的数量，初始容量 只是哈希表在创建时的容量。负载因子 是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 rehash 操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数。
通常，默认加载因子是 0.75, 这是在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销，但同时也增加了查询成本（在大多数 HashMap 类的操作中，包括 get 和 put 操作，都反映了这一点）。在设置初始容量时应该考虑到映射中所需的条目数及其加载因子，以便最大限度地减少 rehash 操作次数。如果初始容量大于最大条目数除以加载因子，则不会发生 rehash 操作。
HashMap在扩容的时候是2的n次幂。

HashMap和LinkedHashMap的区别?

HashMap,LinkedHashMap,TreeMap都属于Map

Map 主要用于存储键(key)值(value)对，根据键得到值，因此键不允许键重复,但允许值重复。

HashMap
是一个最常用的Map,它根据键的HashCode 值存储数据,根据键可以直接获取它的值，具有很快的访问速度。HashMap最多只允许一条记录的键为Null;允许多条记录的值为 Null;HashMap不支持线程的同步，即任一时刻可以有多个线程同时写HashMap;可能会导致数据的不一致。如果需要同步，可以用 Collections的synchronizedMap方法使HashMap具有同步的能力。

LinkedHashMap
LinkedHashMap也是一个HashMap,但是内部维持了一个双向链表,可以保持顺序

TreeMap 可以用于排序

HashMap的例子

public static void main(String[] args) {

  Map<String, String> map = new HashMap<String, String>(); 
 
  map.put("a3", "aa");
 
  map.put("a2", "bb"); 
 
  map.put("b1", "cc");
 
  for (Iterator iterator = map.values().iterator(); iterator.hasNext();)     {
 
        String name = (String) iterator.next(); 
 
        System.out.println(name);   
 
 }  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

输出：bbccaa

LinkedHashMap例子：

public static void main(String[] args) {

 Map<String, String> map = new LinkedHashMap<String, String>();
 
 map.put("a3", "aa");       
 
 map.put("a2", "bb"); 
 
 map.put("b1", "cc"); 
 
 for (Iterator iterator = map.values().iterator(); iterator.hasNext();) {           
 
         String name = (String) iterator.next(); 
 
         System.out.println(name);     
 
 }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

输出：
aa
bb
cc

总结归纳为:linkedMap在于存储数据你想保持进入的顺序与被取出的顺序一致的话，优先考虑LinkedMap，hashMap键只能允许为一条为空，value可以允许为多条为空，键唯一，但值可以多个。

经本人测试linkedMap键和值都不可以为空

HashMap和HashTable有什么区别?

1、HashMap是非线程安全的，HashTable是线程安全的。
2、HashMap的键和值都允许有null值存在，而HashTable则不行。
3、因为线程安全的问题，HashMap效率比HashTable的要高。
4、Hashtable是同步的，而HashMap不是。因此，HashMap更适合于单线程环境，而Hashtable适合于多线程环境。
一般现在不建议用HashTable:
①是HashTable是遗留类，内部实现很多没优化和冗余。
②即使在多线程环境下，现在也有同步的ConcurrentHashMap替代，没有必要因为是多线程而用HashTable