JAVA数据类型

/ lukelee

JAVA数据类型

ArrayList、Vector和LinkedList比较

  1. ArrayList和Vector都是基于存储元素的Object[] array来实现的，它们会在内存中开辟一块连续的空间

    来存储，因为数据存储是连续的，所以它们支持用下标来访问元素，索引数据的速度比较快。

  2. ArrayList和Vector都有一个初始化的容量大小，当里面存储的元素超过初始的大小时就需要动态地扩充

    它们的存储空间，Vector默认扩充为原来的两倍（每次扩充空间的大小可以设置），ArrayList默认

    扩充为原来的1.5倍（没有提供方法来设置空间扩充的方法）。

    Vector(int initialCapacity, int capacityIncrement) //默认 initialCapacity=10 capacityIncrement=2

    public ArrayList(int initialCapacity) //默认 initialCapacity=10 默认扩容1.5倍

    LinkedList没有初始化大小，也没有扩容的机制，就是一直在前面或者后面新增就好

  3. ArrayList和Vector最大的区别就是synchronization的使用，没有一个ArrayList的方法是同步的，而

    Vector的绝大多数方法（如add,insert,remove,set,equals,hashcode）都是直接或间接同步的，所以Vector

    是线程安全的，ArrayList不是线程安全的。正是由于Vector提供了线程安全的机制，其性能上也要稍逊于ArrayList

  4. LinkedList是采用双向列表来实现的，对数据的索引需要从列表头开始遍历，因此用于随机访问则效率比较低，

    但是插入元素时不需要对数据进行移动，因此插入效率较高。同时，LinkedList是非线程安全的容器。

  • 对容器的选择：

    ​ 当对数据的主要操作是索引或只在集合的末端增加、删除元素时，使用ArrayList或Vector效率比较高，

    当对数据的操作主要为指定位置或删除操作时，使用LikedList效率比较高；当在多线程中使用容器时，选用Vector较为安全。

Hashtable、HashMap、TreeMap比较

基本理解

  1. Hashtable、Hashmap、Treemap都是最常见的一些Map实现，是以键值对的形式存储和操作数据的容器类型。

  2. Hashtable是Java类库提供的一个哈希实现，本身是同步的，不支持null键和null值，由于同步导致性能开销，所以已经很少被推荐使用。

  3. HashMap是应用更加广泛的哈希表实现，行为上大致与HashTable一致，主要区别在于HashMap不是同步的，支持null键和null值等。通常情况下HashMap进行get和put操作可以达到常数时间的性能，所以它是绝大部分利用键值对存取场景的首选。

  4. TreeMap则是基于红黑树的一种提供顺序访问的Map，默认按照键的自然顺序进行升序排序，若要进行降序排序则需要在构造集合时候传递一个比较器。

Hashtable中hash数组默认大小是11，增加的方式是 old*2+1。

HashMap中hash数组的默认大小是16，而且一定是2的指数。

TreeMap由红黑树实现，容量方面没有限制。

HashMap和Hashtable相同点

  • HashMap和Hashtable都是存储“键值对(key-value)”的散列表，而且都是采用拉链法实现的。

存储的思想都是：

​ 通过table数组存储，数组的每一个元素都是一个Entry；而一个Entry就是一个单向链表，Entry链表中的每一个节点就保存了key-value键值对数据。

  • 添加key-value键值对：首先，根据key值计算出哈希值，再计算出数组索引(即，该key-value在table中的索引)。然后，根据数组索引找到Entry(即，单向链表)，再遍历单向链表，将key和链表中的每一个节点的key进行对比。若key已经存在Entry链表中，则用该value值取代旧的value值；若key不存在Entry链表中，则新建一个key-value节点，并将该节点插入Entry链表的表头位置。
  • 删除key-value键值对：删除键值对，相比于“添加键值对”来说，简单很多。首先，还是根据key计算出哈希值，再计算出数组索引(即，该key-value在table中的索引)。然后，根据索引找出Entry(即，单向链表)。若节点key-value存在与链表Entry中，则删除链表中的节点即可。

HashMap和Hashtable的不同点

  1. 继承和实现方式不同

    HashMap 继承于AbstractMap，实现了Map、Cloneable、java.io.Serializable接口。 Hashtable 继承于Dictionary，实现了Map、Cloneable、java.io.Serializable接口。

  • HashMap和Hashtable都实现了Map、Cloneable、java.io.Serializable接口。 实现了Map接口，意味着它们都支持key-value键值对操作。支持“添加key-value键值对”、“获取key”、“获取value”、“获取map大小”、“清空map”等基本的key-value键值对操作。 实现了Cloneable接口，意味着它能被克隆。 实现了java.io.Serializable接口，意味着它们支持序列化，能通过序列化去传输。

  • HashMap继承于AbstractMap，而Hashtable继承于Dictionary

    ​ Dictionary是一个抽象类，它直接继承于Object类，没有实现任何接口。Dictionary类是JDK 1.0的引入的。虽然Dictionary也支持“添加key-value键值对”、“获取value”、“获取大小”等基本操作，但它的API函数比Map少；而且 Dictionary一般是通过Enumeration(枚举类)去遍历，Map则是通过Iterator(迭代器)去遍历。 然而‘由于Hashtable也实现了Map接口，所以，它即支持Enumeration遍历，也支持Iterator遍历。关于这点，后面还会进一步说明。

    ​ AbstractMap是一个抽象类，它实现了Map接口的绝大部分API函数；为Map的具体实现类提供了极大的便利。它是JDK 1.2新增的类。

  1. 线程安全不同

    ​ Hashtable的几乎所有函数都是同步的，即它是线程安全的，支持多线程。而HashMap的函数则是非同步的，它不是线程安全的。若要在多线程中使用HashMap，需要我们额外的进行同步处理。 对HashMap的同步处理可以使用Collections类提供的synchronizedMap静态方法，或者直接使用JDK 5.0之后提供的java.util.concurrent包里的ConcurrentHashMap类。

  2. 对null值的处理不同

    ​ HashMap的key、value都可以为null。 ​ Hashtable的key、value都不可以为null。

    ​ Hashtable的key或value，都不能为null！否则，会抛出异常NullPointerException。 ​ HashMap的key、value都可以为null。 当HashMap的key为null时，HashMap会将其固定的插入table[0]位置(即HashMap散列表的第一个位置)；而且table[0]处只会容纳一个key为null的值，当有多个key为null的值插入的时候，table[0]会保留最后插入的value。

  3. 支持的遍历种类不同

    ​ HashMap只支持Iterator(迭代器)遍历，而Hashtable支持Iterator(迭代器)和Enumeration(枚举器)两种方式遍历。

    ​ Enumeration 是JDK 1.0添加的接口，只有hasMoreElements(), nextElement() 两个API接口，不能通过Enumeration()对元素进行修改 。 ​ 而Iterator 是JDK 1.2才添加的接口，支持hasNext(), next(), remove() 三个API接口。HashMap也是JDK 1.2版本才添加的，所以用Iterator取代Enumeration，HashMap只支持Iterator遍历。

  4. 通过Iterator迭代器遍历时，遍历的顺序不同

    ​ HashMap是“从前向后”的遍历数组；再对数组具体某一项对应的链表，从表头开始进行遍历。 ​ Hashtabl是“从后往前”的遍历数组；再对数组具体某一项对应的链表，从表头开始进行遍历。

    ​ HashMap和Hashtable都实现Map接口，所以支持获取它们“key的集合”、“value的集合”、“key-value的集合”，然后通过Iterator对这些集合进行遍历。 ​ 由于“key的集合”、“value的集合”、“key-value的集合”的遍历原理都是一样的；下面，我以遍历“key-value的集合”来进行说明。

    ​ HashMap 和Hashtable 遍历"key-value集合"的方式是：(01) 通过entrySet()获取“Map.Entry集合”。 (02) 通过iterator()获取“Map.Entry集合”的迭代器，再进行遍历。

  5. 容量的初始值 和 增加方式都不一样

    ​ HashMap默认的容量大小是16；增加容量时，每次将容量变为“原始容量x2”。 ​ Hashtable默认的容量大小是11；增加容量时，每次将容量变为“原始容量x2 + 1”。

  6. 添加key-value时的hash值算法不同

    ​ HashMap添加元素时，是使用自定义的哈希算法。 ​ Hashtable没有自定义哈希算法，而直接采用的key的hashCode()。

  7. 部分API不同

    HashMap把Hashtable的contains方法去掉了，改成containsValue和containsKey，因为contains方法容易让人引起误解，没有重写toString()方法。 Hashtable则保留了contains，containsValue和containsKey三个方法，其中contains和containsValue功能相同,而且重写了toString()方法；

HashMap和Hashtable使用的情景

​ 其实，若了解它们之间的不同之处后，可以很容易的区分根据情况进行取舍。例如：(01) 若在单线程中，我们往往会选择HashMap；而在多线程中，则会选择Hashtable。(02)，若不能插入null元素，则选择Hashtable；否则，可以选择HashMap。 ​ 但这个不是绝对的标准。例如，在多线程中，我们可以自己对HashMap进行同步，也可以选择ConcurrentHashMap。当HashMap和Hashtable都不能满足自己的需求时，还可以考虑新定义一个类，继承或重新实现散列表；当然，一般情况下是不需要的了。