Java List集合和哈希表

List集合跟Set集合，先来看List集合。

List集合存储元素的特性：

1.有序（List集合中的元素有下标）：存下去是什么样，取下来还是什么样

2.可重复

可以结合下列的简单代码来看一看。

import java.util.*;
public class ListTest01{
 public static void main(String[] args){
   List l=new ArrayList();
   l.add(100);
   l.add(32);
   l.add(32);
   l.add(90);
   Iterator it=l.iterator();
   while(it.hasNext()){
     System.out.println(it.next());
   }
 }
}

编译运行后输出：

100
32
32
90

由于ArrayList集合底层是函数，数组是有下标的，所以ArrayList集合有很多自己的特点。ArrayList集合底层默认初始化容量是10，扩大以后的容量是原容量的1.5倍。

import java.util.*;
public class ListTest02{
 public static void main(String[] args){
   List l=new ArrayList();
   l.add(12);
   l.add(23);
   l.add(43);
   
   //在下标为1的位置上插入元素
   l.add(1,555);
   //取得第一个元素
   System.out.println(l.get(0));
   System.out.println("-----------");
   for(int i=0;i<l.size();i++){
     Object element=l.get(i);
     System.out.println(element);
   }
 }
}

编译运行后输出：

12
-----------
12
555
23
43

在里面代码中，首先List l=new ArrayList();new出一个新的List对象l,接着使用add()方法添加元素，l.add(a,b)可以在指定的下标为a的位置添加元素b,最后使用for循环遍历输出List l中的元素。注意for循环中的内容为List独有的遍历方式。

Set的推动类主要有HashSet和TreeSet,在讲HashSet之前先来说说什么是哈希表。哈希表（Hash table，也叫散列表），是按照关键码值(Key value)而直接进行访问的数据结构。也就是说list java 容量，它借助把关键码值映射至表中一个位置来访问记录，以加强查找的速率。这个映射函数叫做散列函数，存放记录的字段叫做散列表。

记录的存储位置=f(关键字)

这里的对应关系f称为散列函数，又称为哈希（Hash函数），采用散列技术将记录储存在一块连续的内存空间中，这块连续传输空间称为散列表或哈希表（Hash table）。

哈希表的如下图图示：

哈希表是函数和单向链表的结合，我们都明白数组的特征是轮询容易，插入和删除困难list java 容量，而数组的特征是轮询困难，插入和删除容易，哈希表将两者结合出来，得到了一种寻址容易，插入和删除也容易的数据结构。哈希表本质是一个数组，不过这个数组中的每个元素既都是单向链表，类似于现实世界中的字典。在单向链表的每一个节点，都包括四个组成部分，Object key; Object value; final int hash; Entry next; Entry next指向该结点的下一个节点。final int hash;是一个哈希值，是借助key调用hashCode方法得到的值，再借助“哈希算法”得出的值，并且在单向链表中每一个节点的哈希值是同样的，代表的是函数的下标。如果要对函数中某一个元素进行查找的话该如何做呢？比如要查找一个o对象，o对象去读取hashCode方法，得出哈希值，哈希值代表函数的下标，得到赋值的数组也就明白o对象在哪一个单向链表中。HashMap中有一个方法，Object get[Object key],得到Object value的值。那么怎样往哈希表中添加元素呢？HashMap中有一个添加元素的方式，void put[Object key,Object value];首先调用Object key的hashCode方法，得到一个哈希值，如果哈希值已经存在于函数中，就能定位单向链表，通过key遍历单向链表，如果key与已经存在的key相同（通过equals方法），因为key无序不可重复，所以不添加，反之则在单向链表中添加；若哈希值在函数中不存在，则在数组后面的位置添加一个新的单向链表。因此哈希表的增删效率跟查询效率都是非常高的。从后面的表述中我们了解Object key是十分重要的，不可重复。

搜索微信公众号“程序员考拉”，欢迎关注！

Java List集合和哈希表

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-141791-1.html