精华内容
下载资源
问答
  • 集合代数

    千次阅读 2015-04-19 11:03:19
    集合是精确定义的基本概念。直观地说,把一些事物汇集到一起组成一个整体就叫集合,而这些事物就是这个集合的元素或成员。 设A,B为集合,如果B中的每个元素都是A中的元素,则称B是A的子集合,简称子集。这时也...

    主要内容

    1. 集合,相等,(真)包含,子集,空集,全集,幂集
    2. 交,并,(相对和绝对)补,对称差,广义交,广义并
    3. 文氏图,有穷集计数问题
    4. 集合恒等式(等幂律,交换律,结合律,分配律,德·摩根律,吸收律,零律,同一律,排中律,矛盾律,余补律,双重否定律,补交转换律等)

    学习要求

    1. 熟练掌握集合的子集、相等、空集、全集、幂集等概念及其符号化表示
    2. 熟练掌握集合的交、并、(相对和绝对)补、对称差、广义交、广义并的定义及其性质
    3. 掌握集合的文氏图的画法及利用文氏图解决有限集的计数问题的方法
    4. 牢记基本的集合恒等式(等幂律、交换律、结合律、分配律、德·摩根律、收律、零律、同一律、排中律、矛盾律、余补律、双重否定律、补交转换律)
    5. 准确地用逻辑演算或利用已知的集合恒等式或包含式证明新的等式或包含式
    ===============================================================


    集合的基本概念

    集合的表示

    集合是不能精确定义的基本概念。直观地说,把一些事物汇集到一起组成一个整体就叫集合,而这些事物就是这个集合的元素成员。例如:
      方程x2-1=0的实数解集合;
      26个英文字母的集合;
      坐标平面上所有点的集合;
      ……
      集合通常用大写的英文字母来标记,例如自然数集合N(在离散数学中认为0也是自然数),整数集合Z,有理数集合Q,实数集合R,复数集合C等。
      表示一个集合的方法有两种:列元素法谓词表示法,前一种方法是列出集合的所有元素,元素之间用逗号隔开,并把它们用花括号括起来。例如
              A={a,b,c,…,z}
              Z={0,±1,±2,…}
    都是合法的表示。谓词表示法是用谓词来概括集合中元素的属性,例如集合
              B={x|x∈R∧x2-1=0}
    表示方程x2-1=0的实数解集。许多集合可以用两种方法来表示,如B也可以写成{-1,1}。但是有些集合不可以用列元素法表示,如实数集合。

    集合之间的关系

    下面考虑在同一层次上的两个集合之间的关系。

    定义6.1 设A,B为集合,如果B中的每个元素都是A中的元素,则称B是A的子集合,简称子集。这时也称B被A包含,或A包含B,记作BA。
      如果B不被A包含,则记作BA。
      包含的符号化表示为
          BAx(x∈B→x∈A)
      例如NZQRC,但ZN
      显然对任何集合A都有AA。
      隶属关系和包含关系都是两个集合之间的关系,对于某些集合可以同时成立这两种关系。例如
          A={a,{a}}和{a}
    既有{a}∈A,又有{a}A。前者把它们看成是不同层次上的两个集合,后者把它们看成是同一层次上的两个集合,都是正确的。

    集合的运算

    集合的基本运算

    集合的基本运算有并,交,相对补和对称差。
    定义6.7 设A,B为集合,A与B的并集A∪B,交集A∩B,B对A的相对补集A-B分别定义如下:
          A∪B={x|x∈A∨x∈B }

          A∩B={x|x∈A∧x∈B }

          A-B={x|x∈A∧xB }

      由定义可以看出,A∪B是由A或B中的元素构成,A∩B由A和B中的公共元素构成,A-B由属于A但不属于B的元素构成。例如

          A={a,b,c},B={a},C={b,d}

    则有

          A∪B={a,b,c},A∩B={a},A-B={b,c},

          B-A=,B∩C=

      如果两个集合的交集为,则称这两个集合是不相交的。例如B和C是不相交的。

      两个集合的并和交运算可以推广成n个集合的并和交:

          A1∪A2∪…∪An={x|x∈A1∨x∈A2∨…∨x∈An}

          A1∩A2∩…∩An={x|x∈A1∧x∈A2∧…∧x∈An}

      上述的并和交可以推广成n个集合的并和交:

          =A1∪A2∪…∪An

          =A1∩A2∩…∩An

      并和交运算还可以推广到无穷多个集合的情况:

          =A1∪A2∪…

          =A1∩A2∩…

    有穷计数集

    使用文氏图可以很方便地解决有穷集的计数问题。首先根据已知条件把对应的文氏图画出来。一般地说,每一条性质决定一个集合。有多少条性质,就有多少个集合。如果没有特殊说明,任何两个集合都画成相交的,然后将已知集合的元素数填入表示该集合的区域内。通常从n个集合的交集填起,根据计算的结果将数字逐步填入所有的空白区域。如果交集的数字是未知的,可以设为x。根据题目中的条件,列出一次方程或方程组,就可以求得所需要的结果。

    例6.2 对24名会外语的科技人员进行掌握外语情况的调查。其统计结果如下:会英、日、德和法语的人分别为13,5,10和9人,其中同时会英语和日语的有2人,会英、德和法语中任两种语言的都是4人。已知会日语的人既不懂法语也不懂德语,分别求只会一种语言(英、德、法、日)的人数和会三种语言的人数。
       令A,B,C,D分别表示会英、法、德、日语的人的集合。根据题意画出文氏图如图6.3所示。设同时会三种语言的有x人,只会英、法或德语一种语言的分别为y1,y2和y3人。将x和y1,y2,y3填入图中相应的区域,然后依次填入其它区域的人数。

      根据已知条件列出方程组如下:

        
      解得x=1,y1=4,y2=2,y3=3。

    广义交和广义并

    以上定义的并和交运算称为初级并和初级交。下面考虑推广的并和交运算,即广义并和广义交。
    定义6.10 设A为集合,A的元素的元素构成的集合称为A的广义并,记为∪A。符号化表示为
          ∪A={x|z(z∈A∧x∈z)}。
      例6.4 设  A={{a,b,c},{a,c,d},{a,e,f}},B={{a}},C={a,{c,d}} 则
          ∪A={a,b,c,d,e,f}
          ∪B={a}
          ∪C=a∪{c,d}
          ∪
      根据广义并定义不难证明,若A={ A1,A2,…,An},则∪A=A1∪A2∪…∪An
      类似地可以定义集合的广义交。
    定义6.11 设A为非空集合,A的所有元素的公共元素构成的集合称为A的广义交,记为∩A。符号化表示为
          ∩A={x|z(z∈A→x∈z)}
      考虑例6.4中的集合,有
          ∩A={a},∩B={a},∩C=a∩{c,d}
      细心的读者一定会注意到在定义6.11中特别强调了A是非空集合。对于空集可以进行广义并,即∪。但空集不可以进行广义交,因为∩不是集合,在集合论中是没有意义的。
      和广义并类似,若A={A1,A2,…,An},则∩A=A1∩A2∩…∩An
      在后面的叙述中,若只说并或交,则这都是指集合的初级并或初级交;如果在并或交前边冠以“广义”两个字,则指集合的广义并或广义交。

    集合恒等式

    基本集合恒等式

    下面的恒等式给出了集合运算的主要算律,其中A,B,C代表任意集合。

    • 幂等律   
      • A∪A=A               (6.1)
      • A∩A=A               (6.2)
    • 结合律   
      • (A∪B)∪C=A∪(B∪C)               (6.3)
      • (A∩B)∩C=A∩(B∩C)               (6.4)
    • 交换律   
      • A∪B=B∪A                  (6.5)
      • A∩B=B∩A                  (6.6)
    • 分配律   
      • A∪(B∩C)=(A∪B)∩(A∪C)               (6.7)
      • A∩(B∪C)=(A∩B)∪(A∩C)               (6.8)
    • 同一律   
      • A∪=A                 (6.9)
      • A∩E=A                  (6.10)
    • 零律    
      • A∪E=E                 (6.11)
      • A∩                (6.12)
    • 排中律   
      • A∪~A=E                (6.13)
    • 矛盾律   
      • A∩~A=                (6.14)
    • 吸收律  
      • A∪(A∩B)=A             (6.15)
      • A∩(A∪B)=A              (6.16)
    • 德摩根律  
      • A-(B∪C)=(A-B)∩(A-C)        (6.17)
      • A-(B∩C)=(A-B)∪(A-C)        (6.18)
      • ~(B∪C)=~B∩~C            (6.19)
      • ~(B∩C)=~B∪~C            (6.20)
      • =E               (6.21)
      • ~E=               (6.22)
    • 双重否定律
      •  ~(~A)=A               (6.23)

    证明技巧

    证明技巧一
      除了以上算律以外,还有一些关于集合运算性质的重要结果。 例如:
        A∩BA,A∩BB       (6.24)
        AA∪B,BA∪B       (6.25)
        A-BA            (6.26)
        A-B=A∩~B          (6.27)
    我们只选证其中的一部分。
    例6.9 证明等式6.27,即A-B=A∩~B。
       对于任意的x,
        x∈A-Bx∈A∧xB
            x∈A∧x∈~B
            x∈A∩~B
    所以A-B=A∩~B。
      等式6.27把相对补运算转换成交运算,这在证明有关相对补的恒等式中是很有用的。
    例6.10 证明(A-B)∪B=A∪B
      
            (A-B)∪B
           =(A∩~B)∪B
           =(A∪B)∩(~B∪B)
           =(A∪B)∩E
           =A∪B

    习题

    1.选择适当的谓词表示下列集合:
     (1)小于5的非负整数
     (2)奇整数集合
     (3)10的整倍数的集合
    2.用列元素法表示下列集合:
     (1)S1={x|x是十进制的数字}
     (2)S2={x|x=2∨x=5}
     (3)S3={x|x=x∈Z∧3<x<12}
     (4)S4={x|x∈R∧x2-1=0∧x>3}
     (5)S5={<x,y>|x,y∈Z∧0≤x≤2∧-1≤y≤0}
    3.设F表示一年级大学生的集合,S表示二年级大学生的集合,M表示数学专业学生的集合,R表示计算机专业学生的集合,T表示听离散数学课学生的集合,G表示星期一晚上参加音乐会的学生的集合,H表示星期一晚上很迟才睡觉的学生的集合。问下列各句子所对应的集合表达式分别是什么?请从备选的答案中挑出来。

     (1)所有计算机专业二年级的学生在学离散数学课。
     (2)这些且只有这些学离散数学课的学生或者星期一晚上去听音乐会的学生在星期一晚上很迟才睡觉。
     (3)听离散数学课的学生都没参加星期一晚上的音乐会。
     (4)这个音乐会只有大学一、二年级的学生参加。
     (5)除去数学专业和计算机专业以外的二年级学生都去参加了音乐会。
     备选答案:
     ①TG∪H ②G∪HT ③S∩RT
     ④H=G∪T ⑤T∩G= ⑥F∪SG
     ⑦GF∪S ⑧S-(R∪M)G ⑨GS-(R∩M)
    4.确定下列命题是否为真:
     (1)
     (2)
     (3){}
     (4)∈{}
     (5){a,b}{a,b,c,{a,b,c}}
     (6){a,b}∈{a,b,c,{a,b }}
     (7){a,b}{a,b,{{a,b}}}
     (8){a,b}∈{a,b,{{a,b}}}




    关于Discrete Mathematics更多讨论与交流,敬请关注本博客和新浪微博songzi_tea.


    展开全文
  • 集合基数

    千次阅读 2015-05-12 14:28:08
    通俗的说,集合的势是量度集合所含元素多少的量。集合的势越大,所含的元素越多。 定理9.1 设A,B,C是任意集合,(1) A≈A。(2) 若A≈B,则B≈A。(3) 若A≈B,B≈C,则A≈C。定义9.2 (1) 设A,B是集合,如果存在从A...

    主要内容

    1. 集合的等势与优势 
    2. 集合的基数 

    学习要求


    1. 掌握:集合之间等势与优势的概念,等势的性质(自反性,对称性,传递性) 
    2. 掌握:证明集合等势的方法,康托定理的内容及证明方法 
    3. 掌握:自然数、自然数集、有穷集、无穷集的定义与主要性质 
    4.

    掌握:集合基数的定义、基数的比较、可数集的定义与主要性质

    集合的等势与优势

    集合的等势


      通俗的说,集合的势是量度集合所含元素多少的量。集合的势越大,所含的元素越多。
    定义9.1设A,B是集合,如果存在着从A到B的双射函数,就称A和B是等势的,记作A≈B。如果A不与B等势,则记作AB。
      下面给出一些集合等势的例子。

    例9.1 (1) Z≈N。回顾上一章例8.6(3),令

        f:ZN,

    则f是Z到N的双射函数。从而证明了Z≈N。

      (2) N×N≈N. 为建立N×N到N的双射函数,只需把中所有的元素排成一个有序图形,如图9.1所示。N×N中的元素恰好是坐标平面上第一象限(含坐标轴在内)中所有整数坐标的点。如果能够找到“数遍”这些点的方法,这个计数过程就是建立N×N到N的双射函数的过程。按照图中箭头所标明的顺序,从<0,0>开始数起,依次得到下面的序列:

        <0,0>,<0,1>,<1,0>,<0,2>,<1,1>,<2,0>,…
         ↓   ↓    ↓   ↓   ↓   ↓
         0    1    2    3    4    5

      设<m,n>是图上的一个点,并且它所对应的自然数是k。考察m,n,k之间的关系。首先计数<m,n>点所在斜线下方的平面上所有的点数,是

        1+2+…+(m+n)=
    然后计数<m,n>所在的斜线上按照箭头标明的顺序位于<m,n>点之前的点数,是m.因此<m,n>点是第+m+1个点。这就得到
        k=+m
    根据上面的分析,不难给出N×N到N的双射函数f,即

        f:N×N→N
        f(<m,n>)=+m

    等势的性质


      以上已经给出了若干等势的集合。一般说来,等势具有下面的性质:自反性,对称性和传递性。
      定理9.1 设A,B,C是任意集合,
      (1) A≈A。
      (2) 若A≈B,则B≈A。
      (3) 若A≈B,B≈C,则A≈C。
      证明:根据前面的分析和这个定理可以得到下面的结果:
        N≈Z≈Q≈N×N
        R≈[0,1]≈(0,1)
      而后一个结果可以进一步强化成:任何的实数区间(包括开区间,闭区间以及半开半闭的区间)都与实数集合R等势。那么N与R是否等势呢?如果有N≈R,上面列出的所有集合彼此都是等势的;如果NR,与N等势的那些集合也不会与R等势。下面证明NR。
    定理9.2 (康托定理)
      (1) NR
      (2) 对任意集合A都有AP(A)。
       (1)如果能证明N[0,1],就可以断定NR.为此只需证明任何函数f:N→[0,1]都不是满射的。
      首先规定[0,1]中数的表示。对任意的x∈[0,1],令
        x=0.x1x2…,0≤xi≤9
    考察下述两个表示式:
        0.24999… 和 0.25000…
    显然它们是同一个x的表示。为了保证表示式的唯一性,如果遇到上述情况,则将x表示为0.25000…。根据这种表示法,任何函数f: N→[0,1]的值都可以用这种表示式给出。
      设f: N→[0,1]是从N到[0,1]的任何一个函数。如下列出f的所有函数值:
        f(0)=0.a1(1)a2(1)
        f(1)=0.a1(2)a2(2)
        …
        f(n-1)=0.a1(n)a2(n)
         …
    设y是[0,1]之中的一个小数,y的表示式为0.b1b2…,并且满足bi≠ai(i),i=1,2,….显然y是可以构造出来的,且y与上面列出的任何一个函数值都不相等。这就推出yranf,即f不是满射的。
      (2)和(1)的证明类似,我们将证明任何函数g:A→P(A)都不是满射的。
      设g: A→P(A)是从A到P(A)的函数,如下构造集合B:
        B={x|x∈A∧xg(x)}
    则B∈P(A),但对任意x∈A都有
        x∈Bxg(x)
    从而证明了对任意的x∈A都有B≠g(x)。即Brang。

    优势


      根据这个定理可以知道NP(N)。再综合前边的结果不难断定N{0,1}N。实际上P(N),{0,1}N和R都是比N“更大”的集合。这里的“大”加了引号,因为至今为止我们还没有给出“大小”的严格定义。下面就来进行这个工作。

    定义9.2
      (1) 设A,B是集合,如果存在从A到B的单射函数,就称B优势于A,记作A·B。如果B不是优势于A,则记作A·B。
      (2) 设A,B是集合,若A·B且AB,则称B真优势于A,记作A·B。如果B不是真优势于A,则记作A·B。
      例如N·N,N·R,A·P(A),R·N。 又如N·R,A·P(A),但N·N。
      优势具有下述的性质。
    定理9.3 设A,B,C是任意的集合,则

      (1)A·A。
      (2)若A·B且B·A,则A≈B。
      (3)若A·B且B·C,则A·C。
      定理9.3(2)部分的证明比较复杂,已经超过本书范围,故而略去。(1)和(3)的证明留作练习。

    9.2 集合的基数

    一.后继与归纳集


      上一节我们只是抽象地讨论了集合的等势与优势。下面将进一步研究度量集合的势的方法。最简单的集合是有穷集。尽管前面已经多次用到“有穷集”这一概念,当时只是只管地理解成含有有限多个元素的集合,但一直没有精确地给出有穷集的定义。为解决这个问题我们需要先定义自然数和自然数集合。
     定义9.3 设a为集合,称a∪{a}为a的后继,记作a+,即 a+=a∪{a}。
    例9.3 考虑空集的一系列后继。
        +=∪{}={}
        ++={}+={}∪{{}}={,{}}={+}
        +++={,{}}+={,{}}∪{{,{}}}
            ={,{},{,{}}}
            ={+++}
            …
      由于对任何集合a都有aa。在空集的一系列后继中,任何两个集合都不相等。且满足下面的两个条件:
      1.前边的集合都是后边集合的元素。
      2.前边的集合都是后边集合的子集。
    利用这些性质,可以考虑以构造性的方法用集合来给出自然数的定义,即
        0=
        1=0+=+={}={0}
        2=1+={}+={,{}}={0,1}
        …
        n={0,1,…,n-1}
    但这种定义没有概括出自然数的共同特征。下面我们采用另一种方法刻划自然数。

    自然数,有穷集,无穷集


     定义9.4 设A为集合,如果满足下面的两个条件:
      (1)∈A
      (2)a(a∈A→a+∈A)
    则称A是归纳集
      例如下面的集合
        {,+,++,+++,…}
        {,+,++,+++,…,a,a+,a++,a+++,…}
    都是归纳集。
    定义9.5
      (1)一个自然数n是属于每一个归纳集的集合。
      (2)自然数集N是所有归纳集的交集。
      不难看出,根据定义9.5得到的自然数集N恰好由,+,++,+++,…等集合构成。而这些集合正是构造行所定义的全体自然数。
      鉴于自然数都是集合,有关集合的运算对自然数都是适用的,例如:
        2∪5={0,1}∪{0,1,2,3,4}={0,1,2,3,4}=5
        3∩4={0,1,2}∩{0,1,2,3}={0,1,2}=3
        4-2={0,1,2,3}-{0,1}={2,3}
        2×3={0,1}×{0,1,2}={<0,0>,<0,1>,<0,2>,<1,0>,<1,1>,<1,2>}
        P(1)=P({0})={,{0}}={0,1}
        23={0,1}{0,1,2}={f|f:{0,1,2}→{0,1}}={f0,f1,…,f7}
      其中
        f0={<0,0>,<1,0>,<2,0>}
        f1={<0,0>,<1,0>,<2,1>}
        f2={<0,0>,<1,1>,<2,0>}
        f3={<0,0>,<1,1>,<2,1>}
        f4={<0,1>,<1,0>,<2,0>}
        f5={<0,1>,<1,0>,<2,1>}
        f6={<0,1>,<1,1>,<2,0>}
        f7={<0,1>,<1,1>,<2,1>}

    基数


      下面给出基数的定义。
    定义9.7
      (1)对于有穷集合A,称与A等势的那个唯一的自然数为A的基数,记作cardA,即
        cardA=nA≈n (对于有穷集A,cardA也可以记作|A|)
      (2)自然数集合N的基数记作,即
        cardN=0
      (3)实数集R的基数记作(读作阿列夫),即
        cardR=
      下面定义基数的相等和大小。

    定义9.8 设A,B为集合,则
      (1)cardA=cardBA≈B
      (2)cardA≤cardBA·B
      (3)card<cardBcardA≤cardB∧cardA≠cardB
      根据上一节关于势的讨论不难得到:
        cardZ=cardQ=cardN×N=0
        cardP(N)=card2N=card[a,b]=card(c,d)=
        0<
    其中2N={0,1}N。从这里可以看出,集合的基数是集合的势的大小的度量。基数越大,势就越大。

      由于对任何集合A都满足A·P(A),所以有
        cardA<cardP(A)

    这说明不存在最大的基数。将已知的基数按从小到大的顺序排列就得到:
        0,1,2,…,n,…,0
    其中0,1,2…,n,…,恰好是全体自然数,是有穷集合的基数,也叫有穷基数。而0,…,是无穷集合的基数,也叫做无穷基数0是最小的无穷基数,而后面还有更大的基数,如cardP(R)等。

    可数集


    定义9.9 设A为集合,若cardA≤0,则称A为可数集可列集
      例如{a,b,c},5,整数集Z,有理数集Q,以及N×N等都是可数集,但实数集R不是可数集,与R等势的集合也不是可数集。对于任何的可数集,它的元素都可以排列成一个有序图形。换句话说,都可以找到一个“数遍”集合中全体元素的顺序。回顾前边的可数集,特别是无穷可数集,都是用这种方法来证明的。
      关于可数集有下面的命题:
      1.可数集的任何子集都是可数集。
      2.两个可数集的并是可数集。
      3.两个可数集的笛卡尔积是可数集。
      4.可数个可数集的笛卡尔积仍是可数集。
      5.无穷集A的幂集P(A)不是可数集。
    例9.4 求下列集合的基数。
      (1)T={x|x是单词“BASEBALL”中的字母}
      (2)B={x|x∈R∧x2=9∧2x=8}
      (3)C=P(A),A={1,3,7,11}
       (1)由T={B,A,S,E,L}知cardT=5。
      (2)由B=,可知cardB=0。
      (3)由|A|=4可知cardP(A)=|P(A)|=24=16。
    例9.5 设A,B为集合,且
        cardA=0,cardB=n,n是自然数,n≠0。
    求cardA×B。
       由cardA=0,cardB=n,可知A,B都是可数集。令
        A={a0,a1,a2,…}
        B={b0,b1,b2,…,bn-1}
    对任意的<ai,bj>,<ak,bl>∈A×B有
        <ai,bj>=<ak,bl>i=k∧j=l
    定义函数
        f:A×B→N
        f(<ai,bj>)=in+j,i=0,1,…,j=0,1,…,n-1
    易见f是A×B到N的双射函数,所以
       cardA×B=cardN=0
      如果直接使用可数集的性质,本题的求解更为简单。因为cardA=0,cardB=n,所以A,B都是可数集。根据性质3可知A×B也是可数集,所以cardA×B≤0。显然当B≠时,cardA≤cardA×B,这就推出cardA×B=0

    习题

    1.设A={a,b,c},B=2A,由定义证明P(A)≈2A
    2.设[1,2]和[0,1]是实数区间,由定义证明[1,2]≈[0,1]。
    3.设A={2x|x∈N},证明A≈N。
    4.证明定理9.1。
    5.证明定理9.3的(1),(3)。
    6.设A,B,C,D是集合,且A≈C,B≈D,证明A×B≈C×D。
    7.找出三个不同的N的真子集,使得他们都与N等势。
    8.找出三个不同的N的真子集A,B,C,使得A·N,B·N,C·N。
    9.根据自然数的集合定义计算:
     (1)3∪6,2∩5
     (2)4-3,31
     (3)∪4,∩1
     (4)1×4,22

    10.设A,B为可数集,证明 (1)A∪B是可数集。 (2)A×B是可数集。


    关于Discrete Mathematics更多讨论与交流,敬请关注本博客和新浪微博songzi_tea.

    展开全文
  • 仿射集合和凸集

    千次阅读 2018-09-11 18:27:33
    设是空间的两个点,那么具有下列形式的点: 组成一条穿越和的直线。当参数在0和1之间变动,则构成和之间的线段。 2、仿射集合 如果通过集合中任意两个不同的点的直线仍然在集合C中,则称集合C是仿射的。是仿射...

    1、预备知识:直线和线段

    x_{1}\neq x_{2}R^{n}空间的两个点,那么具有下列形式的点:

    \begin{align*} y&= \theta x_{1} + (1-\theta )x_{2}\\ &= x_{2} + \theta(x_{1}-x_{2}),\theta\in R \end{align*}

    组成一条穿越x_{1}x_{2}的直线。当参数在0和1之间变动,则构成x_{1}x_{2}之间的线段。

    2、仿射集合

    如果通过集合C\subseteq R^{n}中任意两个不同的点的直线仍然在集合C中,则称集合C是仿射的C\subseteq R^{n}是仿射的等价于:对于任意的x_{1},x_{2}\in C\theta \in R\theta x_{1} + (1-\theta )x_{2}\in C

    扩展到多个点:

    仿射组合:如果\theta _{1}+\theta _{2}+...+\theta _{k} = 1,我们称具有\theta _{1}x_{1}+...+\theta _{k}x_{k}形式的点为x_{1},x_{2},...,x_{k}的仿射组合。

    仿射集合:如果C是一个仿射集合,x_{1},x_{2},...,x_{k}\in C,\theta _{1}+\theta _{2}+...+\theta _{k} = 1,那么\theta _{1}x_{1}+...+\theta _{k}x_{k}仍然在C中,即一个仿射集合包含其中任意点的仿射组合。

    仿射包:由集合C\subseteq R^{n}中的点的所有仿射组合组成的集合为C的仿射包,记为aff C:

    aff C = \{\theta _{1}x_{1}+...+\theta _{k}x_{k}|x_{1},...,x_{k}\in C,\theta _{1}+...+\theta _{k}=1\}.

    仿射包是包含C的最小的仿射集合,即若S是满足C\subseteq S的仿射集合,那么aff C\subseteq S

    3、开集和闭集

    内点:对于x\in C\subseteq R^{n},如果存在\epsilon >0满足:\{y|\|y-x\|_{2}\leqslant \epsilon \}\subseteq C,即存在一个以x为中心的的完全属于C的球,则称x为C的内点。

    内部:C的所有内点组成的集合称为C的内部,记为int C

    开集:如果C的每个点都是内点,即int C = C,则称C为开集。

    闭集:如果集合C\subseteq R^{n}的补集R^{n} \ C = \{x\in R^{n}|x\notin C\}是开集,则称C为闭集。

    注(个人理解):可以类比熟知的一维空间的开集、闭集(如开集(1,2),闭集[1,2]),是互通的。

    闭包:记为cl CR^{n} \ int(R^{n} \ C),即C的补集的内部的补集。

    边界:记为 bd C = cl C \ int C。边界点x(即x \in bd C)有如下性质:对于所有\epsilon >0,存在y\in C,z\notin C满足

    \|y-x\|_{2}\leqslant \epsilon ,\|z-x\|_{2}\leqslant \epsilon,即既存在和它任意接近的属于C的点,也存在和他任意接近的不属于C的点(类比开集(1,2),闭集[1,2])。

    用边界刻画开集和闭集:C是闭集的条件是,它包含它的边界;它是开集的条件是,它不含有边界点(类比开集(1,2),闭集[1,2])。

    4、仿射维数与相对内部

    仿射维数:集合C的仿射维数是其仿射包aff C的维数。

    相对内部:集合C的相对内部是其仿射包aff C的内部,记为relint C,即

    relint C = {x\in C|B(x,r)\cap \mathbf{aff} C\subseteq C 对于某些r>0},

    其中B(x,r) = \{y|\|y-x\|\leqslant r\},即半径为r,中心为x并由范数||*||定义的球。

    相对边界:cl C \ relint C,cl C表示C的闭包。

    例子:

    考虑R^{3}中处于(x_{1},x_{2})平面的一个正方形,定义

    C = \{x\in R^{3}|-1\leqslant x_{1}\leqslant 1,-1\leqslant x_{2}\leqslant 1,x_{3}=0\}

    其仿射包为(x_{1},x_{2})-平面,即\mathbf{aff}C= \{x\in R^{3}|x_{3} = 0\},C的内部为空,但其相对内部为

    \mathbf{relint}C = \{x\in R^{3}|-1<x_{1}<1,-1<x_{2}<1,x_{3} = 0\}

    C的边界是其自身,相对边界是其边框\{x\in R^{3}|max\{|x_{1}|,|x_{2}|\}=1,x_{3} = 0\}

    5、凸集

    凸集:如果集合C中任意两点间的线段仍然在C中,即对任意x_{1},x_{2}\in C和满足0\leqslant \theta \leqslant 1\theta都有\theta x_{1}+(1-\theta) x_{2}\in C,则称C是凸集。

    例子:

    凸组合:我们称\theta _{1}x_{1}+...+\theta _{k}x_{k}为点x_{1},x_{2},...,x_{k}的一个凸组合,其中\theta _{1}+\theta _{2}+...+\theta _{k} = 1,且\theta _{i}\geqslant 0,i=1,2,...,k(仿射组合没有\theta _{i}\geqslant 0这个条件)。凸集包含其中所有点的凸组合。

    凸包:集合C中所有点的凸组合的集合为其凸包,记为conv C

    \mathbf{conv}C = \{\theta _{1}x_{1}+...+\theta _{k}x_{k}|x_{i}\in C,\theta _{i}\geqslant 0,i=1,2,...,k,\theta _{1}+...+\theta_{k}=1\}.

    凸包是包含C的最小凸集。即如果B是包含C的凸集,那么\mathbf{conv}C\subseteq B

    微信交流
    多谢打赏

    参考资料:boyd《凸优化》

    展开全文
  • Java集合面试题

    万次阅读 多人点赞 2019-06-25 14:46:19
    Set ,是一个不包含重复元素的集合。这个接口对数学集合抽象进行建模,被用来代表集合,就如一副牌。 List ,是一个有序集合,可以包含重复元素。你可以通过它的索引来访问任何元素。List 更像长度动态...

    Java集合面试题

    Java 集合框架的基础接口有哪些?

    • Collection ,为集合层级的根接口。一个集合代表一组对象,这些对象即为它的元素。Java 平台不提供这个接口任何直接的实现。
      • Set ,是一个不能包含重复元素的集合。这个接口对数学集合抽象进行建模,被用来代表集合,就如一副牌。
      • List ,是一个有序集合,可以包含重复元素。你可以通过它的索引来访问任何元素。List 更像长度动态变换的数组。
    • Map ,是一个将 key 映射到 value 的对象。一个 Map 不能包含重复的 key,每个 key 最多只能映射一个 value 。
    • 一些其它的接口有 Queue、Dequeue、SortedSet、SortedMap 和 ListIterator 。

    ? 为何 Collection 不从 Cloneable 和 Serializable 接口继承?

    Collection 接口指定一组对象,对象即为它的元素。

    • 如何维护这些元素由 Collection 的具体实现决定。例如,一些如 List 的 Collection 实现允许重复的元素,而其它的如 Set 就不允许。
    • 很多 Collection 实现有一个公有的 clone 方法。然而,把它放到集合的所有实现中也是没有意义的。这是因为 Collection 是一个抽象表现,重要的是实现。

    当与具体实现打交道的时候,克隆或序列化的语义和含义才发挥作用。所以,具体实现应该决定如何对它进行克隆或序列化,或它是否可以被克隆或序列化。在所有的实现中授权克隆和序列化,最终导致更少的灵活性和更多的限制,特定的实现应该决定它是否可以被克隆和序列化

    为何 Map 接口不继承 Collection 接口?

    尽管 Map 接口和它的实现也是集合框架的一部分,但 Map 不是集合,集合也不是 Map。因此,Map 继承 Collection 毫无意义,反之亦然。

    如果 Map 继承 Collection 接口,那么元素去哪儿?Map 包含 key-value 对,它提供抽取 key 或 value 列表集合( Collection )的方法,但是它不适合“一组对象”规范。

    ? 为何 Map 接口不继承 Collection 接口?

    尽管 Map 接口和它的实现也是集合框架的一部分,但 Map 不是集合,集合也不是 Map。因此,Map 继承 Collection 毫无意义,反之亦然。

    如果 Map 继承 Collection 接口,那么元素去哪儿?Map 包含 key-value 对,它提供抽取 key 或 value 列表集合( Collection )的方法,但是它不适合“一组对象”规范。

    ? Collection 和 Collections 的区别?

    • Collection ,是集合类的上级接口,继承与他的接口主要有 Set 和List 。
    • Collections ,是针对集合类的一个工具类,它提供一系列静态方法实现对各种集合的搜索、排序、线程安全化等操作。

    ? 集合框架里实现的通用算法有哪些?

    Java 集合框架提供常用的算法实现,比如排序和搜索。

    Collections类包含这些方法实现。大部分算法是操作 List 的,但一部分对所有类型的集合都是可用的。部分算法有排序、搜索、混编、最大最小值。

    ? 集合框架底层数据结构总结

    1)List

    • ArrayList :Object 数组。
    • Vector :Object 数组。
    • LinkedList :双向链表(JDK6 之前为循环链表,JDK7 取消了循环)。

    2)Map

    • HashMap :
      • JDK8 之前,HashMap 由数组+链表组成的,数组是HashMap的主体,链表则是主要为了解决哈希冲突而存在的(“拉链法”解决冲突)。
      • JDK8 以后,在解决哈希冲突时有了较大的变化,当链表长度大于阈值(默认为 8 )时,将链表转化为红黑树,以减少搜索时间。
    • LinkedHashMap :LinkedHashMap 继承自 HashMap,所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外,LinkedHashMap 在上面结构的基础上,增加了一条双向链表,使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作,实现了访问顺序相关逻辑。详细可以查看:《LinkedHashMap 源码详细分析(JDK1.8)》
    • Hashtable :数组+链表组成的,数组是 HashMap 的主体,链表则是主要为了解决哈希冲突而存在的。
    • TreeMap :红黑树(自平衡的排序二叉树)。

    3)Set

    • HashSet :无序,唯一,基于 HashMap 实现的,底层采用 HashMap 来保存元素。
    • LinkedHashSet :LinkedHashSet 继承自 HashSet,并且其内部是通过 LinkedHashMap 来实现的。有点类似于我们之前说的LinkedHashMap 其内部是基于 HashMap 实现一样,不过还是有一点点区别的。
    • TreeSet :有序,唯一,红黑树(自平衡的排序二叉树)。

    什么是迭代器(Iterator)?

    Iterator 接口,提供了很多对集合元素进行迭代的方法。每一个集合类都包含了可以返回迭代器实例的迭代方法。迭代器可以在迭代的过程中删除底层集合的元素,但是不可以直接调用集合的 #remove(Object Obj) 方法删除,可以通过迭代器的 #remove() 方法删除。

    ? Iterator 和 ListIterator 的区别是什么?

    • Iterator 可用来遍历 Set 和 List 集合,但是 ListIterator 只能用来遍历 List。
    • Iterator 对集合只能是前向遍历,ListIterator 既可以前向也可以后向。
    • ListIterator 实现了 Iterator 接口,并包含其他的功能。比如:增加元素,替换元素,获取前一个和后一个元素的索引等等。

    ? 快速失败(fail-fast)和安全失败(fail-safe)的区别是什么?

    差别在于 ConcurrentModification 异常:

    • 快速失败:当你在迭代一个集合的时候,如果有另一个线程正在修改你正在访问的那个集合时,就会抛出一个 ConcurrentModification 异常。 在 java.util 包下的都是快速失败。
    • 安全失败:你在迭代的时候会去底层集合做一个拷贝,所以你在修改上层集合的时候是不会受影响的,不会抛出 ConcurrentModification 异常。在 java.util.concurrent 包下的全是安全失败的。

    ? 如何删除 List 中的某个元素?

    有两种方式,分别如下:

    • 方式一,使用 Iterator ,顺序向下,如果找到元素,则使用 remove 方法进行移除。
    • 方式二,倒序遍历 List ,如果找到元素,则使用 remove 方法进行移除。

    ? Enumeration 和 Iterator 接口有什么不同?

    • Enumeration 跟 Iterator 相比较快两倍,而且占用更少的内存。
    • 但是,Iterator 相对于 Enumeration 更安全,因为其他线程不能修改当前迭代器遍历的集合对象。同时,Iterators 允许调用者从底层集合中移除元素,这些 Enumerations 都没法完成。

    对于很多胖友,可能并未使用过 Enumeration 类,所以可以看看 《Java Enumeration 接口》 文章。

    ? 为何 Iterator 接口没有具体的实现?

    Iterator 接口,定义了遍历集合的方法,但它的实现则是集合实现类的责任。每个能够返回用于遍历的 Iterator 的集合类都有它自己的 Iterator 实现内部类。

    这就允许集合类去选择迭代器是 fail-fast 还是 fail-safe 的。比如,ArrayList 迭代器是 fail-fast 的,而 CopyOnWriteArrayList 迭代器是 fail-safe 的。

    Comparable 和 Comparator 的区别?

    • Comparable 接口,在 java.lang 包下,用于当前对象和其它对象的比较,所以它有一个 #compareTo(Object obj) 方法用来排序,该方法只有一个参数。
    • Comparator 接口,在 java.util 包下,用于传入的两个对象的比较,所以它有一个 #compare(Object obj1, Object obj2) 方法用来排序,该方法有两个参数。

    详细的,可以看看 《Java 自定义比较器》 文章,重点是如何自己实现 Comparable 和 Comparator 的方法。

    ? compareTo 方法的返回值表示的意思?

    • 大于 0 ,表示对象大于参数对象。
    • 小于 0 ,表示对象小于参数对象
    • 等于 0 ,表示两者相等。

    ? 如何对 Object 的 List 排序?

    • Object[] 数组进行排序时,我们可以用 Arrays#sort(...) 方法。
    • List<Object> 数组进行排序时,我们可以用 Collections#sort(...) 方法。

    有哪些关于 Java 集合框架的最佳实践?

    • 基于应用的需求来选择使用正确类型的集合,这对性能来说是非常重要的。例如,如果元素的大小是固定的,并且知道优先级,我们将会使用一个 Array ,而不是 ArrayList 。
    • 一些集合类允许我们指定他们的初始容量。因此,如果我们知道存储数据的大概数值,就可以避免重散列或者大小的调整。
    • 总是使用泛型来保证类型安全,可靠性和健壮性。同时,使用泛型还可以避免运行时的 ClassCastException 异常。
    • 在 Map 中使用 JDK 提供的不可变类作为一个 key,这样可以避免 hashcode 的实现和我们自定义类的 equals 方法。
    • 应该依照接口而不是实现来编程。
    • 返回零长度的集合或者数组,而不是返回一个 null ,这样可以防止底层集合是空的。

    区别

    List 和 Set 区别?

    List,Set 都是继承自 Collection 接口。

    • List 特点:元素有放入顺序,元素可重复。
    • Set 特点:元素无放入顺序,元素不可重复,重复元素会覆盖掉。

    注意:元素虽然无放入顺序,但是元素在 Set 中的位置是有该元素的 hashcode 决定的,其位置其实是固定的。

    另外 List 支持 for 循环,也就是通过下标来遍历,也可以用迭代器,但是 Set 只能用迭代,因为他无序,无法用下标来取得想要的值。

    Set 和 List 对比:

    • Set:检索元素效率高,删除和插入效率低,插入和删除不会引起元素位置改变。
    • List:和数组类似,List 可以动态增长,查找元素效率低,插入删除元素效率,因为可能会引起其他元素位置改变。

    List 和 Map 区别?

    • List 是对象集合,允许对象重复。
    • Map 是键值对的集合,不允许 key 重复。

    Array 和 ArrayList 有何区别?什么时候更适合用 Array?

    • Array 可以容纳基本类型和对象,而 ArrayList 只能容纳对象。
    • Array 是指定大小的,而 ArrayList 大小是固定的,可自动扩容。
    • Array 没有提供 ArrayList 那么多功能,比如 addAll、removeAll 和 iterator 等。

    尽管 ArrayList 明显是更好的选择,但也有些时候 Array 比较好用,比如下面的三种情况。

    • 1、如果列表的大小已经指定,大部分情况下是存储和遍历它们
    • 2、对于遍历基本数据类型,尽管 Collections 使用自动装箱来减轻编码任务,在指定大小的基本类型的列表上工作也会变得很慢。
    • 3、如果你要使用多维数组,使用 [][] 比 List 会方便。

    ArrayList 与 LinkedList 区别?

    ? ArrayList

    • 优点:ArrayList 是实现了基于动态数组的数据结构,因为地址连续,一旦数据存储好了,查询操作效率会比较高(在内存里是连着放的)。
    • 缺点:因为地址连续,ArrayList 要移动数据,所以插入和删除操作效率比较低。

    ? LinkedList

    • 优点:LinkedList 基于链表的数据结构,地址是任意的,所以在开辟内存空间的时候不需要等一个连续的地址。对于新增和删除操作 add 和 remove ,LinedList 比较占优势。LinkedList 适用于要头尾操作或插入指定位置的场景。
    • 缺点:因为 LinkedList 要移动指针,所以查询操作性能比较低。

    ? 适用场景分析

    • 当需要对数据进行对随机访问的情况下,选用 ArrayList 。

    • 当需要对数据进行多次增加删除修改时,采用 LinkedList 。

      如果容量固定,并且只会添加到尾部,不会引起扩容,优先采用 ArrayList 。

    • 当然,绝大数业务的场景下,使用 ArrayList 就够了。主要是,注意好避免 ArrayList 的扩容,以及非顺序的插入。

    ? ArrayList 是如何扩容的?

    直接看 《ArrayList 动态扩容详解》 文章,很详细。主要结论如下:

    • 如果通过无参构造的话,初始数组容量为 0 ,当真正对数组进行添加时,才真正分配容量。每次按照 1.5 倍(位运算)的比率通过 copeOf 的方式扩容。
    • 在 JKD6 中实现是,如果通过无参构造的话,初始数组容量为10,每次通过 copeOf 的方式扩容后容量为原来的 1.5 倍。

    重点是 1.5 倍扩容,这是和 HashMap 2 倍扩容不同的地方。

    ArrayList 集合加入 1 万条数据,应该怎么提高效率?

    ArrayList 的默认初始容量为 10 ,要插入大量数据的时候需要不断扩容,而扩容是非常影响性能的。因此,现在明确了 10 万条数据了,我们可以直接在初始化的时候就设置 ArrayList 的容量!

    这样就可以提高效率了~

    ArrayList 与 Vector 区别?

    ArrayList 和 Vector 都是用数组实现的,主要有这么三个区别:

    • 1、Vector 是多线程安全的,线程安全就是说多线程访问同一代码,不会产生不确定的结果,而 ArrayList 不是。这个可以从源码中看出,Vector 类中的方法很多有 synchronized 进行修饰,这样就导致了 Vector 在效率上无法与 ArrayList 相比。

      Vector 是一种老的动态数组,是线程同步的,效率很低,一般不赞成使用。

    • 2、两个都是采用的线性连续空间存储元素,但是当空间不足的时候,两个类的增加方式是不同。

    • 3、Vector 可以设置增长因子,而 ArrayList 不可以。

    适用场景分析:

    • 1、Vector 是线程同步的,所以它也是线程安全的,而 ArrayList 是线程无需同步的,是不安全的。如果不考虑到线程的安全因素,一般用 ArrayList 效率比较高。

      实际场景下,如果需要多线程访问安全的数组,使用 CopyOnWriteArrayList 。

    • 2、如果集合中的元素的数目大于目前集合数组的长度时,在集合中使用数据量比较大的数据,用 Vector 有一定的优势。

      这种情况下,使用 LinkedList 更合适。

    HashMap 和 Hashtable 的区别?

    Hashtable 是在 Java 1.0 的时候创建的,而集合的统一规范命名是在后来的 Java2.0 开始约定的,而当时其他一部分集合类的发布构成了新的集合框架。

    • Hashtable 继承 Dictionary ,HashMap 继承的是 Java2 出现的 Map 接口。
    • 2、HashMap 去掉了 Hashtable 的 contains 方法,但是加上了 containsValue 和 containsKey 方法。
    • 3、HashMap 允许空键值,而 Hashtable 不允许。
    • 【重点】4、HashTable 是同步的,而 HashMap 是非同步的,效率上比 HashTable 要高。也因此,HashMap 更适合于单线程环境,而 HashTable 适合于多线程环境。
    • 5、HashMap 的迭代器(Iterator)是 fail-fast 迭代器,HashTable的 enumerator 迭代器不是 fail-fast 的。
    • 6、HashTable 中数组默认大小是 11 ,扩容方法是 old * 2 + 1 ,HashMap 默认大小是 16 ,扩容每次为 2 的指数大小。

    一般现在不建议用 HashTable 。主要原因是两点:

    • 一是,HashTable 是遗留类,内部实现很多没优化和冗余。
    • 二是,即使在多线程环境下,现在也有同步的 ConcurrentHashMap 替代,没有必要因为是多线程而用 Hashtable 。

    ? Hashtable 的 #size() 方法中明明只有一条语句 “return count;” ,为什么还要做同步?

    同一时间只能有一条线程执行固定类的同步方法,但是对于类的非同步方法,可以多条线程同时访问。所以,这样就有问题了,可能线程 A 在执行 Hashtable 的 put 方法添加数据,线程 B 则可以正常调用 #size() 方法读取 Hashtable 中当前元素的个数,那读取到的值可能不是最新的,可能线程 A 添加了完了数据,但是没有对 count++ ,线程 B 就已经读取 count 了,那么对于线程 B 来说读取到的 count 一定是不准确的。

    而给 #size() 方法加了同步之后,意味着线程 B 调用 #size() 方法只有在线程 A 调用 put 方法完毕之后才可以调用,这样就保证了线程安全性

    HashSet 和 HashMap 的区别?

    • Set 是线性结构,值不能重复。HashSet 是 Set 的 hash 实现,HashSet 中值不能重复是用 HashMap 的 key 来实现的。

    • Map 是键值对映射,可以空键空值。HashMap 是 Map 的 hash 实现,key 的唯一性是通过 key 值 hashcode 的唯一来确定,value 值是则是链表结构。

      因为不同的 key 值,可能有相同的 hashcode ,所以 value 值需要是链表结构。

    他们的共同点都是 hash 算法实现的唯一性,他们都不能持有基本类型,只能持有对象。

    为了更好的性能,Netty 自己实现了 key 为基本类型的 HashMap ,例如 IntObjectHashMap

    HashSet 和 TreeSet 的区别?

    • HashSet 是用一个 hash 表来实现的,因此,它的元素是无序的。添加,删除和 HashSet 包括的方法的持续时间复杂度是 O(1)
    • TreeSet 是用一个树形结构实现的,因此,它是有序的。添加,删除和 TreeSet 包含的方法的持续时间复杂度是 O(logn)

    ? 如何决定选用 HashMap 还是 TreeMap?

    • 对于在 Map 中插入、删除和定位元素这类操作,HashMap 是最好的选择。
    • 然而,假如你需要对一个有序的 key 集合进行遍历, TreeMap 是更好的选择。

    基于你的 collection 的大小,也许向 HashMap 中添加元素会更快,再将 HashMap 换为 TreeMap 进行有序 key 的遍历。

    HashMap 和 ConcurrentHashMap 的区别?

    ConcurrentHashMap 是线程安全的 HashMap 的实现。主要区别如下:

    • 1、ConcurrentHashMap 对整个桶数组进行了分割分段(Segment),然后在每一个分段上都用 lock 锁进行保护,相对 于Hashtable 的 syn 关键字锁的粒度更精细了一些,并发性能更好。而 HashMap 没有锁机制,不是线程安全的。

      JDK8 之后,ConcurrentHashMap 启用了一种全新的方式实现,利用 CAS 算法。

    • 2、HashMap 的键值对允许有 null ,但是 ConCurrentHashMap 都不允许。

    队列和栈是什么,列出它们的区别?

    栈和队列两者都被用来预存储数据。

    • java.util.Queue 是一个接口,它的实现类在Java并发包中。队列允许先进先出(FIFO)检索元素,但并非总是这样。Deque 接口允许从两端检索元素。
    • 栈与队列很相似,但它允许对元素进行后进先出(LIFO)进行检索。
      • Stack 是一个扩展自 Vector 的类,而 Queue 是一个接口。

    原理

    HashMap 的工作原理是什么?

    我们知道在 Java 中最常用的两种结构是数组和模拟指针(引用),几乎所有的数据结构都可以利用这两种来组合实现,HashMap 也是如此。实际上 HashMap 是一个**“链表散列”**。

    HashMap 是基于 hashing 的原理。

    HashMap 图解

    • 我们使用 #put(key, value) 方法来存储对象到 HashMap 中,使用 get(key) 方法从 HashMap 中获取对象。
    • 当我们给 #put(key, value) 方法传递键和值时,我们先对键调用 #hashCode() 方法,返回的 hashCode 用于找到 bucket 位置来储存 Entry 对象。

    ? 当两个对象的 hashCode 相同会发生什么?

    因为 hashcode 相同,所以它们的 bucket 位置相同,“碰撞”会发生。

    因为 HashMap 使用链表存储对象,这个 Entry(包含有键值对的 Map.Entry 对象)会存储在链表中。

    ? hashCode 和 equals 方法有何重要性?

    HashMap 使用 key 对象的 #hashCode()#equals(Object obj) 方法去决定 key-value 对的索引。当我们试着从 HashMap 中获取值的时候,这些方法也会被用到。

    • 如果这两个方法没有被正确地实现,在这种情况下,两个不同 Key 也许会产生相同的 #hashCode()#equals(Object obj) 输出,HashMap 将会认为它们是相同的,然后覆盖它们,而非把它们存储到不同的地方。

    同样的,所有不允许存储重复数据的集合类都使用 #hashCode()#equals(Object obj) 去查找重复,所以正确实现它们非常重要。#hashCode()#equals(Object obj) 方法的实现,应该遵循以下规则:

    • 如果 o1.equals(o2) ,那么 o1.hashCode() == o2.hashCode() 总是为 true 的。
    • 如果 o1.hashCode() == o2.hashCode() ,并不意味 o1.equals(o2) 会为 true

    ? HashMap 默认容量是多少?

    默认容量都是 16 ,负载因子是 0.75 。就是当 HashMap 填充了 75% 的 busket 是就会扩容,最小的可能性是(16 * 0.75 = 12),一般为原内存的 2 倍。

    ? 有哪些顺序的 HashMap 实现类?

    • LinkedHashMap ,是基于元素进入集合的顺序或者被访问的先后顺序排序。
    • TreeMap ,是基于元素的固有顺序 (由 Comparator 或者 Comparable 确定)。

    ? 我们能否使用任何类作为 Map 的 key?

    我们可以使用任何类作为 Map 的 key ,然而在使用它们之前,需要考虑以下几点:

    • 1、如果类重写了 equals 方法,它也应该重写 hashcode 方法。

    • 2、类的所有实例需要遵循与 equals 和 hashcode 相关的规则。

    • 3、如果一个类没有使用 equals ,你不应该在 hashcode 中使用它。

    • 4、用户自定义 key 类的最佳实践是使之为不可变的,这样,hashcode 值可以被缓存起来,拥有更好的性能。不可变的类也可以确保hashcode 和 equals 在未来不会改变,这样就会解决与可变相关的问题了。

      比如,我有一个 类MyKey ,在 HashMap 中使用它。代码如下:

      //传递给MyKey的name参数被用于equals()和hashCode()中
      MyKey key = new MyKey('Pankaj'); //assume hashCode=1234
      myHashMap.put(key, 'Value');
      // 以下的代码会改变key的hashCode()和equals()值
      key.setName('Amit'); //assume new hashCode=7890
      //下面会返回null,因为HashMap会尝试查找存储同样索引的key,而key已被改变了,匹配失败,返回null
      myHashMap.get(new MyKey('Pankaj'));
      
      
      • 那就是为何 String 和 Integer 被作为 HashMap 的 key 大量使用。

    ? HashMap 的长度为什么是 2 的幂次方?

    为了能让 HashMap 存取高效,尽量较少碰撞,也就是要尽量把数据分配均匀,每个链表/红黑树长度大致相同。这个实现就是把数据存到哪个链表/红黑树中的算法。

    这个算法应该如何设计呢?我们首先可能会想到采用 % 取余的操作来实现。但是,重点来了:

    • 取余(%)操作中如果除数是 2 的幂次则等价于与其除数减一的与(&)操作(也就是说 hash % length == hash & (length - 1) 的前提是 length 是 2 的 n 次方;)。
    • 并且,采用二进制位操作 &,相对于 % 能够提高运算效率,

    这就解释了 HashMap 的长度为什么是 2 的幂次方。

    HashSet 的工作原理是什么?

    HashSet 是构建在 HashMap 之上的 Set hashing 实现类。让我们直接撸下源码,代码如下:

    // HashSet.java
    
    private transient HashMap<E,Object> map;
    
    private static final Object PRESENT = new Object();
    
    
    • map 属性,当我们创建一个 HashMap 对象时,其内部也会创建一个 map 对象。后续 HashSet 所有的操作,实际都是基于这个 map 之上的封装。

    • PRESENT 静态属性,所有 map 中 KEY 对应的值,都是它,避免重复创建。

    • OK ,再来看一眼 add 方法,代码如下:

      // HashSet.java
      
      public boolean add(E e) {
          return map.put(e, PRESENT) == null;
      }
      
      
      • 是不是一目了然。

    ? HashSet 如何检查重复?

    艿艿:正如我们上面看到 HashSet 的实现原理,我们自然可以推导出,HashMap 也是如何检查重复滴。

    如下摘取自 《Head First Java》 第二版:

    当你把对象加入 HashSet 时,HashSet会先计算对象的hashcode值来判断对象加入的位置,同时也会与其他加入的对象的hashcode值作比较。

    • 如果没有相符的 hashcode ,HashSet会假设对象没有重复出现。
    • 但是如果发现有相同 hashcode 值的对象,这时会调用 equals 方法来检查 hashcode 相等的对象是否真的相同。
      • 如果两者相同,HashSet 就不会让加入操作成功。
      • 如果两者不同,HashSet 就会让加入操作成功

    【详细可以查看java基础系列】

    展开全文
  • 集合框架 1.1 集合框架概述 1.1.1 容器简介 到目前为止,我们已经学习了如何创建多个不同的对象,定义了这些对象以后,我们就可以利用它们来做一些有意义的事情。  举例来说,假设要存储许多雇员,不同的...
  • 先看一张描述java.util.concurrent包下集合组成结构的类图: 下列介绍的集合统一特性:线程安全,支持并发操作 非阻塞队列(队列无数据,操作队列产生异常或返回null,不具备等待/阻塞的特色) ...
  • 集合与通用集合

    千次阅读 2004-08-30 15:50:00
    -->集合与通用集合???龚永生(gongys@lenovo.com)2003年7月 本文描述了Jakarta项目commons-collection,其当前版本是2.1版。本文对j2sdk集合框架的整理和例子示例可以大大加快程序员熟悉和使用集合,文中的例子
  • 先看一张描述java.util.concurrent包下集合组成结构的类图 下列介绍的集合统一特性:线程安全,支持并发操作 非阻塞队列(队列无数据,操作队列产生异常或返回null,不具备等待/阻塞的特色) ConcurrentHashMap...
  • Java集合排序及java集合类详解

    万次阅读 2012-08-20 14:21:53
    集合是Java里面最常用的,也是最重要的一部分。能够用好集合和理解好集合对于做Java程序的开发拥有无比的好处。本文详细解释了关于Java中的集合是如何实现的,以及他们的实现原理。   目录 1 集合框架............
  • Java集合框架完全解析

    千次阅读 多人点赞 2017-05-23 12:57:43
    1、集合概述 现实生活中集合:很多事物凑在一起。  数学中的集合:具有共同属性的事物的总体。  Java中的集合类:是一种工具类,就像是容器,储存任意数量的具有共同属性的对象。在编程时,常常需要集中存放多个...
  • 集合论与图论

    千次阅读 多人点赞 2020-06-23 10:21:20
    文章目录一、集合及其运算1.1 集合概念1.2 子集、集合相等定义1.2.1 集合的包含.定义1.2.2 集合的真子集.定义1.2.3 集合的相等.定理1.2.1 空集定义1.2.4 集族.定义1.2.5 幂集.1.3 集合的基本运算定义1.3.1 并集定理...
  • 多种嵌入式文件系统移植集合

    万次阅读 2013-06-01 21:23:34
    1.1. 计算机组成原理 从冯.诺依曼的存储程序工作原理及计算机的组成来说,计算机由运算器、控制器、存储器和输入/输出设备五大部件组成。其中运算器和控制器统称为中央处理器(CPU),而存储系统分成内部存储器(内存)...
  • Java集合容器全面分析

    千次阅读 2016-08-07 17:45:17
    简介: 集合类Collection不是Java的核心类,是Java的扩展类。集合可以用来储存任何类型的对象...(Generics type)编程概念和技术应用于集合类,解决了集合类的类型安全问题,这可用于对任何数据类型的定义和操作。
  • 可变集合Set set函数创建集合 创建空集合 集合元素的唯一性 集合推导式 set类型对象的内置方法 add增加一个元素 remove删除一个元素 pop随机删除并返回一个元素 discard删除一个元素 clear 不可变集合Frozenset ...
  • 离散数学(一)——集合

    千次阅读 2019-08-25 14:51:52
    1.集合:集合是一些对象的主体,对象有时也可以看做元素或成员。     例如等式A={1,2,3,4},描述了由1、2、3、4四个元素组成的集合A。     集合与元素的特定顺序无关。A也...
  • 集合(三)

    千次阅读 2018-05-18 11:48:55
    Java集合框架提供了一套性能优良、使用方便的接口和类,...其中 Collection集合包含两个常用的子集合-----List和Set(1)List集合常用子类ArrayList Vector(2) Set集合常用子类HashSet TreeSet LinkedHashSet M...
  • Delphi 集合 使用资料收集

    千次阅读 2013-10-20 10:12:45
     delphi中的集合是对数学中集合的概念的简单实现。要求是集合中的元素必须同类型,且必须是序数类型,且集合中可能的元素个数不大于255。  定义: type 集合类型名 = set of 元素类型  例如: type MySet = set...
  • ConvertHelper与泛型集合

    千次阅读 热门讨论 2014-10-30 22:21:45
    在机房重构时,我们经常会用到ConvertHelper。它把从数据库中查询到的dateTable(也是一个临时表)...二是因为它的返回值是泛型集合,泛型集合使存储数据时灵活而安全,也体现了面向对象的思想。 ConvertHelper与sqlHelpe
  • 计算机组成原理习题——日常记录

    千次阅读 多人点赞 2020-02-21 17:07:57
    计算机组成原理习题 软件分为两种,分别是系统软件和应用软件 冯·诺依曼型计算机的主要特点是什么?(5点) 1. 计算机由五大部件组成 2. 指令和数据采用二进制表示 ...写出下列专有名词英文缩写代表的...
  • java.util.List 接口继承自 Collection 接口,是单列集合的一个重要分支,习惯性地会将实现了 List 接口的对象称为List集合。 List集合有以下特点: 在List集合中允许出现重复的元素(通过元素的equals方法来比较...
  • C# 获取List集合中指定几行的数据

    千次阅读 2019-11-29 14:52:46
    最近在做一个项目需要获取list集合中指定几行的数据,如何快速获取。 #region 构造方法(Start) /// <summary> /// 构造方法 /// </summary> public class MonthClass { public string Id { ...
  • 计算机组成原理

    千次阅读 2013-10-26 15:32:36
    计算机组成原理   【考查目标】 1. 理解单处理器计算机系统中各部件的...3. 能够运用计算机组成的基本原理和基本方法,对有关计算机硬件系统中的理论和实际问题进行计算、分析,并对一些基本部件进行简单设计。
  • 1.从键盘输入整数x,判断它是否是集合a,b,c的元素,若是分别输出1,2,3,若都不是输出4,要求集合a从键盘输入,请补充程序 2.创建由Monday~Sunday(代表...5.随机生成10个[0,10]范围的整数,分别组成集合A和集合B
  • MongoDB中的集合类似于关系型数据库中的表,mongodb中的文档类似于关系型数据库中的行。...多个文档组成一个集合, 多个集合组成一个数据库。这里mongdb版本是3.2 常用命令创建一个集合use MyDB; // 如果
  • 计算机组成原理习题集

    千次阅读 2019-03-18 22:05:59
    控制器理解、解释并执行所有的指令及存储结果(控制器不执行、存储) B.一台计算机包括输人、输出、控制、存储及算术逻辑运算五个部件 C.所有的数据运算都在CPU的控制器中完成(显卡是独立的数据运算,GPU,...
  • 编译原理-求FOLLOW集合

    千次阅读 2018-05-04 14:54:41
    前言 为什么需要求FIRST集合:因为一个产生式存在多个候选式,选择哪一个候选式是不确定的,所以这就产生了回溯。回溯需要消耗大量的计算、...为什么需要求FOLLOW集合:求FOLLOW集合的目的和FIRST集合的目的是一...
  • 计算机组成期末复习

    千次阅读 2020-11-22 19:03:12
    ( c )1、在下列四句话中,最准确反映计算机主要功能的是下面哪项。 A.计算机可以存储大量信息 B.计算机代替人的脑力劳动 C.计算机是一种信息处理机 D.计算机可实现高速运算 ( c )2、计算机硬件直接...
  • 传统的集合运算包括并,差,交,笛卡儿积运算 1.并 关系R和关系S的所有元组合并,再...关系R和关系S的交是由既属于R又属于S的元组组成集合,即在两个关系R和S中取相同的元组,组成一个新关系 4.笛卡儿积运算 在这里指
  • Java集合基础知识总结(绝对经典)

    千次阅读 多人点赞 2020-06-12 15:20:56
    一、数组Array和集合的区别 1、数组是大小固定的,并且同一个数组只能存放类型一样的数据(基本类型/引用类型) 2、JAVA集合可以存储和操作数目不固定的一组数据。 3、若程序时不知道究竟需要多少对象,需要在...
  • 集合是多个元素的无序组合 集合元素之间无序 集合由不可变数据类型元素组成,如整数、浮点数、复数,字符串、元组类型等 集合用大括号{}组成,元素之间用逗号隔开 每个元素唯一,不存在相同元素 一、集合间...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 56,239
精华内容 22,495
关键字:

下列能组成集合的是