集合总体大纲,不可变的字典类

问题

试验楼python挑衅赛1兑现一个不可变的dict,数据只好由类先导化的时候经过参数字传送递,修改、增加都会抛出TypeError

前言

Java集合是java提供的工具包,包涵了常用的数据结构:集结、链表、队列、栈、数组、映射等。Java集合工具包地方是java.util.*

Java集合重要能够分开为几个部分:List列表、Set集结、Map映射、工具类(Iterator迭代器、Enumeration枚举类、Arrays和Collections)。

Java集结工具包框架图(如下):

图片 1

image.png

消除措施

雄起雌伏ABCs中的MultiMapping, 复写在那之中的1部分方法就可以。

正文

看上边的框架图,先抓住它的骨干,即Collection和Map。

代码

import collections


class ImmutableDict(collections.MutableMapping):
 def __init__(self, **kwargs):
     self.store = dict(**kwargs)
     self.error = TypeError("'ImmutableDict' objects are immutable")
     # self.update(dict(*args, **kwargs))

 def __setitem__(self, key, value):
     # 涉及到修改时会触发这个方法
     raise self.error

 def __iter__(self):
     return iter(self.store)

 def __delitem__(self, key):
     # 删除时触发
     raise self.error

 def __getitem__(self, key):
     return self.store[key]

 def __len__(self):
     return len(self.store)


class Get(object):
 def __init__(self):
     pass

 def __getitem__(self, item):
     return hash(item)


if __name__ == "__main__":
 test = ImmutableDict(name="sun", age=22, location="China")
 # test["name"] = "zhang"
 # test.pop("name")   TypeError will raised..
 # print(test.pop("name"))
 # for item in test:
     # print(item)
     #print(test[item])

MultiMapping 源码:

class MutableMapping(Mapping):

    @abstractmethod
    def __setitem__(self, key, value):
        raise KeyError

    @abstractmethod
    def __delitem__(self, key):
        raise KeyError

    __marker = object()

    def pop(self, key, default=__marker):
        try:
            value = self[key]
        except KeyError:
            if default is self.__marker:
                raise
            return default
        else:
            del self[key]
            return value

    def popitem(self):
        try:
            key = next(iter(self))
        except StopIteration:
            raise KeyError
        value = self[key]
        del self[key]
        return key, value

    def clear(self):
        try:
            while True:
                self.popitem()
        except KeyError:
            pass

    def update(self, other=(), **kwds):
        if isinstance(other, Mapping):
            for key in other:
                self[key] = other[key]
        elif hasattr(other, "keys"):
            for key in other.keys():
                self[key] = other[key]
        else:
            for key, value in other:
                self[key] = value
        for key, value in kwds.items():
            self[key] = value

    def setdefault(self, key, default=None):
        try:
            return self[key]
        except KeyError:
            self[key] = default
        return default

MutableMapping.register(dict)

Mapping 源码:

class Mapping(Sized, Iterable, Container):

    @abstractmethod
    def __getitem__(self, key):
        raise KeyError

    def get(self, key, default=None):
        try:
            return self[key]
        except KeyError:
            return default

    def __contains__(self, key):
        try:
            self[key]
        except KeyError:
            return False
        else:
            return True

    def iterkeys(self):
        return iter(self)

    def itervalues(self):
        for key in self:
            yield self[key]

    def iteritems(self):
        for key in self:
            yield (key, self[key])

    def keys(self):
        return list(self)

    def items(self):
        return [(key, self[key]) for key in self]

    def values(self):
        return [self[key] for key in self]

    # Mappings are not hashable by default, but subclasses can change this
    __hash__ = None

    def __eq__(self, other):
        if not isinstance(other, Mapping):
            return NotImplemented
        return dict(self.items()) == dict(other.items())

    def __ne__(self, other):
        return not (self == other)

分析四个难题:

  • .get 的时候到底发生了怎么?
  • .pop 的时候发出了怎么着?

品味进行断点调节和测试:

尝试

get 跳转到了Mapping中的get

image.png

image.png

专注其中的self正是我们实例化的immutableDict类

敲定:
.get展现定义是在Mapping中,可是Mapping又把这些点子的落到实处抛给了子类,事实上,便是调用了
immutableDict.getitem中的方法。
从而我们在get 会触发我们在 immutableDict.getitem中定义的老大
pop 也就很类似了。

Collection接口、子接口以及贯彻类

Collection接口

  • 是List、Set和Queue接口的父接口

  • 概念了可用于操作List、Set和Queue的章程-增删改查

Collection接口API中定义的艺术如下:

图片 2

image.png

List接口

  • List是因素有序并且能够再次的集结,被喻为连串

  • List可以标准的决定每种成分的插入地方,或删除有个别地方成分

  • List接口的常用子类:

    ArrayList

    LinkedList

    Vector

    Stack

下图是List的JDK源码UML图。

图片 3

image.png

Set接口

  • Set接口中不可能进入重复成分,冬季

  • Set接口常用子类:

    散列存放:HashSet

    以不改变应万变存放:TreeSet

下图是Set的JDK源码UML图。

图片 4

image.png

Map和HashMap

Map接口

  • Map提供了1种炫丽关系,个中的成分是以键值对(key-value)的花样累积的,能够落到实处基于key飞快找寻value

  • Map中的键值对以Entry类型的目的实例格局存在

  • 键(key值)不可重复,value值可以

  • 每一个建最八只好照射到3个值

  • Map接口提供了独家再次回到key值会集、value值集结以及Entry(键值对)会集的格局

  • Map协理泛型,方式如:Map<K,V>

HashMap类

  • HashMap是Map的三个要害完结类,也是最常用,基于哈希表完成

  • HashMap中的Entry对象是冬季排列的

  • Key值和Value值都得感到null,不过三个HashMap只可以有三个key值为null的照射(key值不可重复)

下图是Map的JDK源码UML图

图片 5

image.png

Comparable和Comparator

Comparable接口——可正如的

  • 福寿年高该接口表示:那么些类的实例能够十分的大小,能够举行自然排序

  • 概念了暗中认可的可比规则

  • 实则现类必要完结compareTo()方法

  • compareTo()方法重临正数表示大,负数表示小0代表格外

Comparator接口——相比较工具接口

  • 用来定义不常相比规则,而不是默许比较规则

  • 实际上现类供给贯彻compare()方法

  • Comparable和Comparator都是Java集结框架的积极分子

Iterator接口

  1. 汇合输出的正儿八经操作

    正规做法,使用Iterator接口

  2. 操作原理:

    Iterator是特地的迭代输出接口,迭代出口正是将成分3个个实行决断,决断其是或不是有内容,借使有内容则把内容收取。

总结

集结的效率

  • 在类的内部,对数码实行协会;

  • 简单来说而敏捷的找出大数据的条条框框;

  • 1部分集合接口,提供了一名目大多排列有序的要素,并且能够在系列中间飞速的插入或然去除有关因素;

  • 局地群集接口,提供了炫酷关系,能够经过机要字(key)去飞快找出对应的唯一指标,而那一个首要字额能够是随意档次。

与数组的争论统一—————为什么采用集结而不是数组

  • 数组的长度固定,集结长度可变

  • 数组只可以通过下标访问成分,类型定位,而有些集合能够经过自由档案的次序查找所映射的有血有肉对象。

整理的集合框架思维导图

图片 6

image.png


初稿链接:http://www.jianshu.com/p/5dcb98e4b3d2