很多python初学者经常会有这样的疑问，为什么Python有tuple（元组）和list（列表）两种类型？为什么tuple可以作为字典的key，list不可以？要理解这个问题，首先要明白python的字典工作原理。
Python的字典是如何工作的
在Python中，字典也就是一个个的“映射”，将key映射到value：
# 对一个特定的key可以得到一个value value = d[key]
为了实现这个功能，Python必须能够做到，给出一个key，找到哪一个value与这个key对应。先来考虑一种比较简单的实现，将所有的key-value键值对存放到一个list中，每当需要的时候，就去遍历这个list，用key去和键值对的key匹配，如果相等，就拿到value。但是这种实现在数据量很大的时候就变得很低效。它的算法复杂度是O(n)，n是存放键值对的数量。
为此，Python使用了hash（哈希）的方法来实现，要求每一个存放到字典中的对象都要实现hash函数，这个函数可以产生一个int值，叫做hash value（哈希值），通过这个int值，就可以快速确定对象在字典中的位置。
这个查询的大致过程如下：
def lookup(d, key): ”’字典的查询过程概括为下面3步: 1. 通过hash函数将key计算为哈希值. 2. 通过hash值确定一个位置，这个位置是一个存放着 可能存在冲突的元素的数组（很多地方叫做“桶”，bucket）， 每一个元素都是一个键值对，理想情况下，这个数组里只有1个元素. 3. 遍历这个数组，找到目标key，返回对应的value. ”’ h = hash(key)# step 1 cl = d.data[h]# step 2 for pairin cl:# step 3 if key == pair[0]: return pair[1] else: raise KeyError, “Key %s not found.” % key
要使这个查找过程正常工作，hash函数必须满足条件： 如果两个key产生了不同的hash value，那么这两个key对象是不想等的。 即
for alli1, i2, if hash(i1) != hash(i2), then i1 != i2
否则的话，hash value不同，对象却相同，那么相同的对象产生不同的hash value，查找的时候就会进错桶（step 2），在错误的桶里永远也找不到你要找的value。
另外，要让字典保持高查找效率，还要保证： 当两个key产生相同的hash value，那么他们是相等的。
for alli1, i2, if hash(i1) == hash(i2), then i1 == i2
这样做的目的是，尽量满足每个hash桶只有一个元素。为什么要这样呢？ 考虑下面这个hash函数。
def hash(obj): return 1
这个hash函数是满足上面我们谈的第一个条件的：如果两个key的hash value不同，那么两个key对象不相同。因为所有的对象产生的hash value都是1，所以不存在能产生不同hash value的key，也就不存在不满足的情况。但是这样做的坏处是，因为所有的hash value都相同，所以就把所有的对象分到了同一个地方。查找的时候，进行到第三步，遍历的效率就变成了O(n).
Hash函数应该保证所有的元素平均的分配到每一个桶中，理想的情况是，每一个位置只有一个元素。
字典Key要满足的要求
经过上面的讨论，我们应该明白Python为什么对字典的key有这样的要求了：
要作为字典的key，对象必须要支持hash函数（即__hash__），相等比较(__eq__或__cmp__），并且满足上面我们讨论过的条件。
List为什么不能作为key
至于这个问题，最直接的答案就是：list没有支持__hash__方法，那么为什么呢？
对于list的hash函数，我们可能有下面两种实现的方式：
第一种，基于id。这满足条件，“如果hash值不同，那么他们的id当然不同”。但考虑到list一般是作为容器，基于id来hash可能会导致下面两种情况：
用相同的list作为key去字典中找某个元素可能会得到不同的结果，因为是基于id hash的，所以即使他们的内容相同，字典依然将他们作为不同的元素对待。 创建一个一模一样的list用字典查找永远会得到一个KeyError。
第二种，基于内容。tuple就是这样做的，但是要注意一点，list是可以修改的。当list修改之后，你就永远别想再从字典中拿回来了。见下面的代码。
>>> l = [1, 2] >>> d = {} >>> d[l] = 42 >>> l.append(3) >>> d[l] # 原来的hash值是基于[1, 2]hash的， # 现在是基于[1, 2, 3]，所以找不到 Traceback (mostrecentcalllast): File “”, line 1, in ? KeyError: [1, 2, 3] >>> d[[1, 2]] # 基于hash [1, 2] # 但是遍历的时候找不到key相等的键值对 #（因为字典里的key变成了[1, 2, 3] Traceback (mostrecentcalllast): File “”, line 1, in ? KeyError: [1, 2]
鉴于两种实现的方式都存在一定的副作用，所以Python规定：
内置的list不能作为字典的key.
但tuple是不可变，所以tuple可以作为字典的key。
自定义的类型作为字典的Key
用户自定义的类型就可以作为key了，默认的 hash(object) 是 id(object) , 默认的 cmp(object1,object2) 是 cmp(id(object1),id(object2))， 同样是可以修改的对象，为什么这里就没有上面说的问题呢？
一般来说，在映射中比较常见的需求是用一个object替换掉原来的，所以id比内容更重要，就可以基于id来hash 如果内容重要的话，自定义的类型可以通过覆盖__hash__函数和__cmp__函数或__eq__函数来实现
值得注意的是：将对象和一个value关联起来，更好的做法是将value设置为对象的一个属性。

1.集合类型主要有3种：set(集）、list(列表）和map(映射)
2.三者关系

3.Set
set接口时Collection接口的一个子接口，是无序的，set中不包含重复的元素，也就是说set中不存在两个这样的元素a1.equals(a2)结果为true。又因为Set接口提供的数据结构是数学意义上的集合概念的抽象，因此他支持对象的添加和删除。
Set的接口继承Collection接口，而且不允许集合中存在重复项。
TreeSet：在集中以升序对对象排序的集的实现，这意味着从一个TreeSet对象获得第一个迭代器将按照升序来提供对象，TreeSet类使用了一个TreeMap
下面来看一个例子，当需要从一个Set集合中以有序的方式抽取元素时，TreeSet实现会有用处，为了能顺利进行，添加到TreeSet的元素必须是可排序的。
public class Collection_test {
 
	public static void main(String[] args) {
		
		Set<String> set = new HashSet<String>();
		set.add("xet");
		set.add("jpo");
		set.add("wo");
		set.add("jpo");
		System.out.println(set);
 
		Set<String> softset = new TreeSet<String>(set);
		System.out.println(softset);
	}
}

可以看到上面的输出是无序的，且没有重复，下面的输出就是按照首字母的顺序进行排序


4.List
List接口继承了Collection接口以定义一个允许重复项的有序集合。
一般有2种List，一种是基本的ArrayList，其优点在于随机访问元素，另一种是更强大的LinkedList,他并不是为了快速随机访问而设计的，而是具有一套更通用的方法
List最重要的特点就是:它保证维护元素特定的顺序，List为Collection添加了很多方法，使得能够向List中间插入语移除元素。
ArrayList:由数组实现的List，允许对元素进行快速随机访问，但是向List中间插入与移除元素的速度很慢。
LinkedList:对顺序访问进行了优化，向List中间插入与删除的开销并不大，随机访问则行对较慢，（使用ArrayList代替）还有下列方法：addFirst(),addLast(),getFirst(),getLast(),removeFirst(),romoveLast().这些方法使得LinkedList可以当作堆栈，队列和双向队列使用。
List的一些API的使用：
public class Collection_test {
 
	
	public static void main(String[] args) {
		
		List l1 = new LinkedList();
		for(int i = 0;i<=5;i++){
			l1.add("a"+i);
		}
		System.out.println(l1);
		//向指定位置加一个字符串
		l1.add(0,"a100");
		System.out.println(l1);
		//替换index=6的位置的字符串
		l1.set(6, "a200");
		System.out.println(l1);
		//取index=2的位置的字符串
		System.out.println(l1.get(2)+"");
		//获得a3的index索引编号
		System.out.println(l1.indexOf("a3"));
		//移除index=1的值
		l1.remove(1);
		System.out.println(l1);
	}
}

List的常用算法举例
/**
 * List常用算法举例
 */

List p1 = new LinkedList();
List p2 = new LinkedList();
for(int i = 0; i<=9;i++){
	p1.add("a"+i);
}
//打印p1[a0, a1, a2, a3, a4, a5, a6, a7, a8, a9]
System.out.println(p1);
//随机排列
Collections.shuffle(p1);
System.out.println(p1);
//逆序
Collections.reverse(p1);
System.out.println(p1);
//排序
Collections.sort(p1);
System.out.println(p1);
//折半查找
System.out.println(Collections.binarySearch(p1, "a5"));

}
5.set 和List的对比
Colllection是集合接口

Set子接口：无序，不允许存在重复的元素
List子接口：有序，可以存在重复元素

区别，Collection是集合类
Set 和List的对比：
Set：检查元素效率低下，删除和插入的效率高，插入和删除不会引起元素的位置变化。
List：和数组类似，List可以动态增长，查找元素的效率较高，插入元素和删除元素效率低，因为会引起其他元素位置发生变化。
Set 和 List的具体子类：
Set

HashSet：以哈希表的形式存放元素，插入删除速度很快

List：

ArrayList :动态数组
LinkedList:链表，队列，堆栈

6.Map
Map接口不是Collection接口的继承，而是从自己的用于维护键值对关联的接口层次结构入手，按定义，该接口描述了从不重复的键到值的映射。
一般可以分为三组操作：改变，查询和提供可选视图
Map.Entry 接口
Map的entrySet()方法返回一个实现Map.Entry接口的对象集合。集合中每个对象都是底层Map中一个特定的键-值对。
通过这个集合迭代，您可以获得每一条目的键或值并对值进行更改。但是，如果底层Map在Map.Entry接口的setValue()方法外部被修改，此条目集就会变得无效，并导致迭代器行为未定义。
HashMap： 实现一个映象，允许存储空对象，而且允许键是空（由于键必须是唯一的，当然只能有一个）。
映射的使用示例：
以下程序演示了具体Map类的使用。该程序对自命令行传递的词进行频率计数。HashMap起初用于数据存储。后来，映射被转换为TreeMap以显示有序的键列列表。
import java.util.*;
 
public class MapExample {
　　public static void main(String args[]) {
　　　　Map map = new HashMap();
　　　　Integer ONE = new Integer(1);
　　　　for (int i=0, n=args.length; i<n; i++) {
　　　　　　String key = args[i];
　　　　　　Integer frequency = (Integer)map.get(key);
　　　　　　if (frequency == null) {
　　　　　　　　frequency = ONE;
　　　　　　} else {
　　　　　　　　int value = frequency.intValue();
　　　　　　　　frequency = new Integer(value + 1);
　　　　　　}
　　　　　　map.put(key, frequency);
　　　　}
　　　　System.out.println(map);
　　　　Map sortedMap = new TreeMap(map);
　　　　System.out.println(sortedMap);
　　}
}

结果：
//无序输出：
{prescribed=1, a=1, time=2, any=1, no=1, shall=1, nor=1, peace=1, owner=1, soldier=1, to=1, the=2, law=1, but=1, manner=1, without=1, house=1, in=4, by=1, consent=1, war=1, quartered=1, be=2, of=3}
//有序输出：
{a=1, any=1, be=2, but=1, by=1, consent=1, house=1, in=4, law=1, manner=1, no=1, nor=1, of=3, owner=1, peace=1, prescribed=1, quartered=1, shall=1, soldier=1, the=2, time=2, to=1, war=1, without=1}

1、什么是Iterator
一些集合类提供了内容遍历的功能，通过java.util.Iterator接口。这些接口允许遍历对象的集合。依次操作每个元素对象。当使用 Iterators时，在获得Iterator的时候包含一个集合快照。通常在遍历一个Iterator的时候不建议修改集合本省。
2、Iterator与ListIterator有什么区别？
Iterator：只能正向遍历集合，适用于获取移除元素。ListIerator：继承Iterator，可以双向列表的遍历，同样支持元素的修改。
3、什么是HaspMap和Map？
Map是接口，Java 集合框架中一部分，用于存储键值对，HashMap是用哈希算法实现Map的类。
4、HashMap与HashTable有什么区别？对比Hashtable VS HashMap
两者都是用key-value方式获取数据。Hashtable是原始集合类之一（也称作遗留类）。HashMap作为新集合框架的一部分在Java2的1.2版本中加入。它们之间有一下区别：

HashMap和Hashtable大致是等同的，除了非同步和空值（HashMap允许null值作为key和value，而Hashtable不可以）。
HashMap没法保证映射的顺序一直不变，但是作为HashMap的子类LinkedHashMap，如果想要预知的顺序迭代（默认按照插入顺序），你可以很轻易的置换为HashMap，如果使用Hashtable就没那么容易了。
HashMap不是同步的，而Hashtable是同步的。
迭代HashMap采用快速失败机制，而Hashtable不是，所以这是设计的考虑点。

5、在Hashtable上下文中同步是什么意思？
同步意味着在一个时间点只能有一个线程可以修改哈希表，任何线程在执行hashtable的更新操作前需要获取对象锁，其他线程等待锁的释放。
6、什么叫做快速失败特性
从高级别层次来说快速失败是一个系统或软件对于其故障做出的响应。一个快速失败系统设计用来即时报告可能会导致失败的任何故障情况，它通常用来停止正常的操作而不是尝试继续做可能有缺陷的工作。当有问题发生时，快速失败系统即时可见地发错错误告警。在Java中，快速失败与iterators有关。如果一个iterator在集合对象上创建了，其它线程欲“结构化”的修改该集合对象，并发修改异常 （ConcurrentModificationException） 抛出。
7、怎样使Hashmap同步？
HashMap可以通过Map m = Collections.synchronizedMap（hashMap）来达到同步的效果。
8、什么时候使用Hashtable，什么时候使用HashMap
基本的不同点是Hashtable同步HashMap不是的，所以无论什么时候有多个线程访问相同实例的可能时，就应该使用Hashtable，反之使用HashMap。非线程安全的数据结构能带来更好的性能。
如果在将来有一种可能—你需要按顺序获得键值对的方案时，HashMap是一个很好的选择，因为有HashMap的一个子类 LinkedHashMap。所以如果你想可预测的按顺序迭代（默认按插入的顺序），你可以很方便用LinkedHashMap替换HashMap。反观要是使用的Hashtable就没那么简单了。同时如果有多个线程访问HashMap，Collections.synchronizedMap（）可以代替，总的来说HashMap更灵活。
最后
感谢大家看到这里，文章有不足，欢迎大家指出；如果你觉得写得不错，那就给我一个赞吧。
也欢迎大家关注我的公众号：程序员麦冬，麦冬每天都会分享java相关技术文章或行业资讯，欢迎大家关注和转发文章！