什么是数组?
数组大家应该都非常熟悉我们来简单的回顾一下:
1.数组是一个具有连续的内存空间和相同类型的数据的数据结构
2.我们随机访问任意一个下标的数据的时间复杂度都是 O(1)
3但是正是由于这种特性,导致它插入和删除元素的效率比较低,是 O(n)
![](data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAPUAAAD4CAYAAAA0L6C7AAAgAElEQVR4nO2df3QTdb7339PSwgSxtAltbQUiuKTWu7fVDXrdwKqAl6hce55Wyj6G9J7nAW/rrq5Pn0t1D2yENQvnesDtWWW71cNznr2EePeymz64qxB2hdUtcY+au1iP1gZtSautUJKWWMm0tHSeP+qMkzS/2jRJM/28zslpZvKd73yS5jWf73znm/kyPM/zIAhCNmSkOgCCIGYWkpogZMa8RFZOLXuCiAzDMDNe54xKTRITxNQIdmYmJJ8RqUlmgpgZBJfikTsuqacqM8lPzHVilTUeuZnpXNKKZZPgMiQ0QUwQLGos4k5F7ilJHa0oz/Mhy5DQBBFIKEkZhokqb0wHgFiljlRsfHw85rKxvE4QcmOqsmZkhL/aHLWuWKQOl32jNbGDZY9WJ0HIkUgSBssbqmkeLquH3V80qUO9HC4zRxNdWo4g5hKChFIZIwkcS+YOJ3ZEqaMJHU5moUwoiUloYq4SSmjhr1TacHLHKvaULmkFCx0stbAslXqqQpP0RLoy1V7sUE3rSE3t8fHxiOfaAmGljtaMjvYQggjeJlTdc4mvvvoK1113XarDIJKMNPOGyr48z4uvSR/B2wvlBIKXgRgzdbisLDzGx8fB8zyys7ORlZU1nfcse65evYp7770X2dnZAIA333wz4PU9e/Zg9+7dUevpODTzY4XnGiXbZ2dSGR0dxdWrV8EwTNimdiyDUkJKHSorS58Hy8zzPLKyskjoMIyMjGDDhg0oLS2F2WxGYWFhXPWVPOicocjmHh2va1MdQliysrLA8zxGR0cxPj4eUu5QYgdn6ymdU0vllgo9Pj4uZiBiMjt37kRpaSleeumlVIdCzHKys7MxMjIiyiycRwsyx3LePknqcOfSkbL1tWvX4n4zcuXixYt48cUX8cUXX6Q6FCJNEHySnm8LQgf/FZAuR8zU0TrHBKEjDTKZ69jtdmzatAlKpTLVoRBpgtSnjIyMSVeRwjW7BQKkjiVLj4+PT3pQpg7PO++8g3Xr1qU6DCKNEHwKNQAllmwd0+2Mwo0Uk0pOhKa9vR233XZbqsMg0gjBqUjeRSLqdergJnhwlhbWEaH57LPPsHLlylSHQaQRQueY4FWoa9zhsjUQ4caDsRwhpHITofF4PMjPz091GEQaEc6rWH5EBUikjpTSg3u+g7M0SR0ajuNw5cqVmIb2EYRAKL9iHZHJ83z0c+pIl7So+R0ZlmVhMplSHQaRZki9Ch56HYvYIaWO9YggDYAIzZ49e1IdApFmSBNlrC1oKTG3C0MdLcL10BEEMX2kLWFhWbo+GhEzdajlUDskqQli5gj+pWOwY9E6y6bUgxNceSxNBIIgpoZUaOm6WD2bUvM72nNi7uHq7Eb5hkfAFGlhbTkBAOCGR1D39D4wRVowRVqYGw9NWl/39D5wwyOpDD0qVqtVvDas1+vh9XqntD3Hcairq4PD4ZjyvuPxLebe70ivU+/33KZgSR46Wm0wVN4PADjwKwuKC/PB9znh73Kg90I/rC0nwC6Yj+bnduLIQXOKI46Ow+GAxWKBx+MBz/MwGo3YtWsXOI6LaXuO41BfXz+tX+bF0vk85d7vWCqgDD13CM680qwcjKuzG2fefR/VD90HAGAXzIfx4QfR+s7ZWZ+ZBTiOg8VigdFoFH+Io9fr4fP50NPTA6vVivLycrhcLrF8XV0dzOaJg5XVaoVCoQAAbNy4Ma5YpuMejYogIsINj6B+9/Ni5uX7nDhy0Iz9TRa4OrsnlfcMXAbDMFDlLRbXqfIW43xPH3p6LyQz9Gnj9/vhdruhVqvFdQqFAjk5OXA6nTAYDKiqqsLRo0cBAC0tLQCAHTt2AADy8/Ph8Xiwd+/e5AePJM+lRaQfQpNZirasFAVL8sJuo156AxTsAnFZlbcYeYuvT1iMiSA3NxcqlUpcZlkWxcXF4nJ1dTW2bNmCgoIC2Gw2vPDCC2BZFgBw330TrZSpnoMHM12/4s7UJPbcwdx4CEyRFiVrq3Dx0kCqw0kpGo0GDQ0NqK2tRU1NDTQazYzWH49X1PwmoiLI3HuhH/4uBzpabREztfuzL+DnhsVlz8BlDFz+MhmhzhiDg4PweDziMsdx6O3tDVm2q6srWWHFxJSlpsw8t/AO+tB+rgsdrTY0P7cT7IL5Ecur8haD53l4Bi6L6zwDl3HTsiIsK47vhovJQqFQQK1Ww+12i+v8fj98Ph+02okbF7pcLhw+fBjHjh2DzWab1mWrqTAV72YkU5Po8mbQNyRK6h304UnTgbDNb83K5VhzRzmO/v5PACY62iy/ex1r77wt6gFhtsCyLIxGIywWi3hebLfbkZOTg2XLloHjODQ2NqKmpgYVFRVoaGiA2WyO+xxaIF6fqPlNRESZmwNT/XasqdgGpkiL9Zsfg6l+OwrzlXC2tYfcZsdjRvRe6AdTpIVihQ7FhfniNex0QafTwWg0QqVSgWEYWCwW7N27FyzL4sCBA3C73dDr9QCAyspKqNVqNDU1pTjqCcS5tMIN/wy+08nY2BiuXbuGsbExjI6Oio9Vq1al5h3McqT3aZ4JOg4xs+q+367ObvzoJ/vxws8aoFm5PKZtrC0n0PrOWTT+9F+Tnr07XtfO2pv5C5w7d068j35WVhbmzZuHzMxMzJs3DxkZGQGPUHNxUaYmCJlBUhNxc/HSAErWVoUdZSYgjEzb+jjdOCKRxDX4hCA0K5fj/TdeiamsMJAleDALMbNQpiYImUFSE4TMIKkJQmaQ1AQhM0hqgpAZJDVByAySmiBkBklNEDKDpCYImUFSE4TMIKkJQmbQ2O80pON1bapDIGYxJHUaMpt+T51uzIUDIjW/CUJmkNQEITNIaoKQGSQ1QcgMkpogZAZJTRAyg6QmCJlBUhOEzCCpCUJmkNQEITNIaoKQGSQ1QcgMkpogZAZJTcSFq7Mb5RseAVOknTSXljB3luO9toBlpkiLuqf3gRseSUXIMWO1WsEwDBiGgV6vj3n+aa/XC71eL25rNpsTHGkgJDURNwVL8tDRaguYg5obHkH97ufxkqVFXCfMpXXkYHK/5NPB4XDAYrHA4/GA53kYjUbs2rULHMdF3M7r9cJgMMBoNILnefj9fvT29sJqtSYpcpKaiAFphhUekWa4tLacgGKFDgCw8Z67khXmjMFxHCwWC4xGI5RKJQBAr9fD5/Ohp6cHVqsV5eXlcLlcYvm6ujqYzWZ0dHSI5QGAZVkYjUa0trZGPSDMFCQ1EREh4xYX5oPvc4Lvc+LIQTP2N1ng6uwOuU2+Kg+ej05h749/mORoZwa/3w+32w21Wi2uUygUyMnJgdPphMFgQFVVFY4ePQoAaGmZaI3s2LEDOp0OdrtdPBgAgNvtTmr8dOcTIiJCk1mKtqwUBUvywm5z3/fuBAB4B30JjS2R5ObmQqVSicssy6K4uFhcrq6uxpYtW1BQUACbzYYXXngBLMtOqsfr9cJiscBkMoV8PRFQpiZixtx4CEyRFiVrq3Dx0kCqw0kpGo0GDQ0NqK2tRU1NDTQazaQywvm1TqeDTqdLWmwkNREVQebeC/3wdznQ0WqLmKnlwODgIDwej7jMcRx6e3tDlu3q6pq0Tiq0yWRKWJyhIKmJiHgHfWg/14WOVhuan9sJdsH8VIeUcBQKBdRqdcC5sN/vh8/ng1Y7ceNCl8uFw4cP49ixY7DZbHA4HGJZl8uF9evXw2g0Jl1ogKQmYmDQNwTPwGUAE5I/aTog6+a30GNtsVjEa9N2ux05OTlYtmwZOI5DY2MjampqUFFRgYaGBpjNZni9Xni9Xjz55JNoaGiAwWBISfwkNRERZW4OTPXbsaZiG5giLdZvfgym+u0ozFfC2dae6vAShk6ng9FohEqlAsMwsFgs2Lt3L1iWxYEDB+B2u8XLVpWVlVCr1WhqaoLdbsfJkyexdetWcfDJVAevxAv1fhNR0a0uA98XeK9x+ysvAkDYy1rAxAFBKJeOGAyGkNk2uEnNsiyam5sDtksllKkJQmaQ1ETcXLw0gJK1VRFHmQHfjEzb+njyO4/mEtT8JuJCs3I53n/jlZjKCgNZggezEDMLZWqCkBkkNUHIDJKaIGQGSU0QMoOkJgiZQVIThMwgqQlCZpDUBCEzSGqCkBkkNUHIDJKaIGQGjf1OQzpe16Y6BGIWQ1KnISUPOqMXIkIyFw6I1PwmCJlBUhOEzCCpCUJmkNQEITNIaoKQGSQ1QcgMkpogZAZJTRAyg6QmCJlBUieYzMzMVIdAzDFI6gQyPj6OhQsXpjoMYo5BUieQ/v5+qFSqVIdBzDGSKrXD4YDZbAYAWK1WWK1WcByHp556Ci6XCy6XC0899RQ4jgu5vdlshtVqTWbIcdHZ2YmlS5emOgxijpFUqXU6HVasWCGKeeXKFezevRvbtm2DRqOBx+NBWVkZWJadtK3L5cLQ0BAqKyvF5fLy8oDpQoXHbBH/7NmzKC0tTXUYCcXV2Y3yDY+AKdKKc2l5B33QP/IEmCItmCItzI2HAHwzlxZTpEXd0/vADY+kMvSoWK3WaU1Fy3Ec6urqUvZ9TKrUZrMZW7duFR+1tbXYv38/tmzZApfLhdOnT0+a11fI7MePH8e2bdvg9/uh1+vx1ltv4ZZbboHH4wHP8+Lj2WefTeZbisjp06dx5513pjqMhFOwJA8drTYYKu+Hd9AHww9/AuPDD4Dvc8Lf5UDvhX5YW06Ic2kdOWhOdchRcTgcsFgs4vfLaDRi165dYVuRAhzHob6+HsXFxeB5Hh6PBxaLBQ6HI0mRJ1lqk8kEnudx5MgRAMCRI0fA8zzef/99AEB7e7v4IZ45cwbPPvssTCYTHA4H8vPzodFoYLfbodPpcPfdd0fdn9frhV6vj/iBms3mkAeRePF6vXjttdfEicnTGWmGFR7hZrjs+NQNANDf+10AE5PiGR9+EK3vnJ31mVmA4zhYLBYYjUYolUoAgF6vh8/nQ09PD6xWK8rLy+FyucTydXV1MJvN6Onpwfnz51FdXQ0AUCqV0Ol0OH36dNLiT6rUwpu3WCz4+c9/jq1bt4rNmuPHjyMnJ0cs63a7sWLFCgAIyOAWiwU/+MEPAAAff/wxVCpVgJTPPPOMWIdSqRQPAqEwm83o7e2F3+8XDyTPPPPMjBxVd+7ciSeeeAIFBQVx15VKuOER1O9+HsWF+eD7nOD7nDhy0Iz9TZaQE87rVpfB/sqLUOZK/pef9SUz5Ljx+/1wu91Qq9XiOoVCgZycHDidThgMBlRVVeHo0aMAgJaWFgDAjh07oNFocPLkSWg0GgATB3eHw4F169YlLf6kSS00S9auXQu73Y78/HwcOXIEJpMJKpUKLpcLt99+Ozo6OsBxHFpbW8UP1WQywe/3o6GhAb/4xS/Eo2e8zW+TyYTm5mbxHL6kpAQbN26M631euHABjz76KNrb27Fv37646poNCE1mU/12cZ22rBQFS/Ji2t476IPld8dhfPhBsAvmJyrMGSc3NzfgygXLsiguLhaXq6urYbPZ8PLLL+Pw4cOor68P6AsSEphKpYJOpwubWBJB0qRmWRbNzc0wGAxiE9dgMECn04HneTQ3N+PWW2/F6dOn0dPTA5/Ph5KSEgDfHBAqKirEI+BMInSIqFQqnDx5ckrbLliwQGwl5Obm4oYbbsChQ4fw8ccfw2azzXisqcTceAhMkRYla6tw8dJA1PLC+bVudRl0q8uSEGHy0Gg0aGhoQG1tLWpqaiZ9L4XvO8/zWLFiBerq6qKej88USc3UQo/gM888E9AhJkheUlKC9vZ2/OhHP0JpaamYkf/2t7/hpZdewpo1a8AwjPgBRWt+R0OQWegQ8Xg8U87Uw8PDYithcHAQX375JXiex29+8xvs2bMHX3zxxZTqm40IMvde6Ie/y4GOVlvUTC0VWprl04XBwUF4PB5xmeM49Pb2hizb1dUVsS6tVovz58+jp6dnRmMMR1Iz9d69e/H9738fHR0d4Hkefr8ftbW14vmGUqnEpk2bwDCMeN4MQMzmwkNoMsfT/Baa+GfOnIHdbhcPIPGyaNEiAMCGDRtQUFCAv/zlLzNSb6rwDvrQfq4LHa02ND+3M6YmtKuzG+s3Pwbjww+kpdAKhQJqtRput1tc5/f74fP5oNVO3LjQ5XLh8OHDOHbsGGw2m9gP43A4pnT5KxEktaPM6/Xipz/9KZ588kkwDAOFQoG1a9eK5xsulwv79+/HyZMnYbfbJ20v9FTr9fqAo2g8CP84juOwa9euKTe/I6HX63H27NkZqy9VDPqG4Bm4DGBC8idNB8I2v4XXG35ghKHy/mSGOWOwLAuj0QiLxSLKabfbkZOTg2XLloHjODQ2NqKmpgYVFRVoaGiA2WyG1+vF7bffDrVaLX5/hbJr1qxJyKljKJIq9apVq8DzPC5cuICysjI0NDRg69atcDgcsFqtKCkpwS9/+Uvx2p509BnDMFi3bh14nofdbo9p+GWkS1osy6K+vh779+8XDzBVVVWora2dscsPd9xxBz755JMZqStVKHNzYKrfjjUV28AUabF+82Mw1W9HYb4Szrb2SeXtf34bJ9/8K7Y+bgq4BKZ/5Al4B30peAfTQ6fTwWg0iqd3FosFe/fuBcuyOHDgANxut3i5srKyEmq1Gk1NTWKL1GKxiN+r4uJimEympMXO8DzPA8DXfwBM/BBBWDc+Ph7wGBsbw7Vr1zA2NobR0VHxsWrVqog7Ejq73G43rFZrQHPXbDaLYgevBzDpAzGbzVHPnYVr3Kmku7sbmzdvxrvvvjtjdXYcYmbVfb9dnd340U/244WfNUCzcnlM21hbTqD1nbNo/Om/Jr1HvON1LUq289ELppBz584hKytLfMybNw+ZmZmYN28eMjIyAh4MwwAAMjK+yc9Ju5m/0BsYinDyRVqfamFjobi4GJcuXUp1GMQcg36llUDmzZsHny99mpzT5eKlAZSsrQo7ykxAGJm29fHZf0BOZ2janQTj9/tTHUJC0axcjvffeCWmssJAlubndiY4qrkNZeoEMzo6muoQiDkGSZ1gpjIYhiBmApI6wezZsyfVIRBzDJKaIGQGSU0QMoOkJgiZQVIThMwgqQlCZpDUBCEzSGqCkBkkNUHIDBr7nYZ0vK5NdQjELIakTkNm0++p0425cECk5jdByAySmiBkBklNEDKDpCYImUFSE4TMIKkJQmaQ1AQhM0hqgpAZJDVByAySmiBkBklNEDKDpCYImUFSE4TMIKmJuHB1dqN8wyNgirTiXFrCnFnCNLah1tc9vQ/c8EgqQ4+KMIWyMCf6dCaST8Uk9CQ1ETcFS/LQ0WqDofJ+cMMjqN/9PIoL88H3OeH56BQsvzsOx3tt4lxaRw6aUx1yVBwOBywWCzweD3ieh9FoxK5du8BxXMx1eL1ecTrmZEJSE1EJzrzS7BtMT+8FnO/pQ/VD9wGYmLRet7oMp8+8l8yQ44LjOFgsFhiNRnG+dL1eD5/Ph56eHlitVpSXl8Plconl6+rqJgnc1NQEnU6X9PhJaiIiwZmX73PiyEEz9jdZ4OrsnlRes3I5Tv7HQXECeu+gD4732rBuzepkhz5t/H4/3G431Gq1uE6hUCAnJwdOpxMGgwFVVVU4evQoAKClpQUAsGPHDrG8w+EAAKxbty6JkU9Adz4hIiI0maVoy0pRsCQv4nbCweAlSwuebaiDbnVZIsOccXJzc6FSqcRllmVRXFwsLldXV2PLli0oKCiAzWbDCy+8AJZlAUxk7ldffRXbtm2Dx+NJeuyUqYmYMTceAlOkRcnaKly8NBCxrHAw4PucWLG8OC06xqaCRqNBQ0MDamtrUVNTA41GI77W0tKCsrKygHXJhKQmoiLI3HuhH/4uBzpabVEztRRtWSnO9/Shp/dCAqOcWQYHBwOyLMdx6O3tDVm2q6tLfO5yudDW1obKysqExxgOkpqIiHfQh/ZzXehotaH5uZ1gF8yPWN7xXhv0jzwB76AvSRHOPAqFAmq1Gm63W1zn9/vh8/mg1U7cuNDlcuHw4cM4duwYbDabeA7tdDqxf/9+KBQKMAyDNWvW4OTJk1i/fr3YsZZoSGoiKoO+IXgGLgOYkPxJ04Gwze/bv10C9dIbYP/z2wAmzq0bX7ZizR3lYufZbIdlWRiNRlgsFvH6st1uR05ODpYtWwaO49DY2IiamhpUVFSgoaEBZrMZXq8XBoMBPM+LjzNnzmDjxo04depU0prjJDUREWVuDkz127GmYhuYIi3Wb34MpvrtKMxXwtnWPqk8u2A+9v74h7D87jiYIi0UK3QoLsyHqX57CqKfPjqdDkajESqVCgzDwGKxYO/evWBZFgcOHIDb7YZerwcAVFZWQq1Wo6mpKcVRT0C930RUdKvLwPcF3mvc/sqLABDyspYyN0d8PZ0xGAwwGAyT1ptMpoBllmXR3Nwcsg6dTge73Z6Q+MJBmZogZAZJTcTNxUsDKFlbFXaUmYAwMm3r46aI5Yj4oOY3ERealcvx/huvxFRWuHYdPJiFmFkoUxOEzCCpCUJmkNQEITNIaoKQGSQ1QcgMkpogZAZJTRAyg6QmCJlBUhOEzCCpCUJmkNQEITNo7Hca0vG6NtUhELMYkjoNKXnQGb0QEZK5cECk5jdByAySmiBkBklNEDKDpCYImUFSE4TMIKkJQmaQ1AQhM0hqgpAZJDVByAySmiBkBklNEDKDpCYImUFSE4TMIKmJuHB1dqN8wyNgirQh59KSTkIvzKXFFGlR9/Q+cMMjKYg4dqxWKxiGAcMw0Ov14lzV0XC5XCgvLxe3ZRgGZrM5wdF+A0lNxE3Bkjx0tNpgqLw/YL130Adz4yFxWZhL68jB5H3Bp4vD4YDFYoHH4wHP8zAajdi1axc4jou6rdPpRENDQ8Dk88HT3yYSkpqIijTDCo9oM1wCQNOvfwvd6rIkRDizcBwHi8UCo9EIpVIJANDr9fD5fOjp6YHVakV5eTlcLpdYvq6uTszGXV1dUKvVKYufpCYiwg2PoH738yguzAff5wTf58SRg2bsb7KEnHBewPFeGwBg3ZrVyQp1xvD7/XC73QFiKhQK5OTkwOl0wmAwoKqqCkePHgUAtLS0AAB27NgBjuMwNDSEZ599NiVNb4CkJqIgNJlN9dvFddqyUhQsyQu7DTc8gldPvoXqh+5LRogJITc3FyqVSlxmWRbFxcXicnV1NWw2G15++WUcPnwY9fX1YFkWfr8fH3zwAWpqasDzPPx+P3p7e+mcmpidmBsPgSnSomRtFS5eGghbruX4aZSVfgualcuTGF1y0Wg0aGhoQG1tLWpqaqDRaAAASqUSdrsdBoMBwMTBoL6+HmfOnBGb64mGpCaiIsjce6Ef/i4HOlptYTO1q7Mbbe2foPKBdUmOcmYZHByEx+MRlzmOQ29vb8iyXV1dEetSqVTIywvfsplpSGoiIt5BH9rPdaGj1Ybm53aCXTA/YnlnWzv2Nx2GYoUOTJEWayq24eSbf8X6zY9FPAefTSgUCqjVarjdbnGd3++Hz+eDVjtx40KXy4XDhw/j2LFjsNlscDgcACZ6zYMvfwkHB2lzPpGQ1ERUBn1D8AxcBjAh+ZOmA2Gb34bK+8UONb7PiTOv/h9svOcunPrtr9KmOc6yLIxGIywWiyin3W5HTk4Oli1bBo7j0NjYiJqaGlRUVKChoQFmsxlerxclJSVieQBi2U2bNok96YmGpCYioszNgal+O9ZUbANTpMX6zY/BVL8dhflKONvaUx1ewtDpdDAajVCpVGAYBhaLBXv37gXLsjhw4ADcbjf0ej0AoLKyEmq1Gk1NTVAqlbBarbBYLGAYBgqFAsXFxeI5djKg+34TUdGtLgPfF3ivcfsrLwJA1Ca1bnWZWDbdMBgMIWUMHkjCsiyam5vFZaGzLFXMSKZmGGYmqiEIAvH7NGWpSWAimIuXBlCytirqKDNhZNrWx5M3ZFIuTMU7an4TcaFZuRzvv/FKTGWFgSzNz+1McFRzm7ib35S5CWLmiceruKQmoSPz1VdfpToEIo2Zrl90SSuBZGZmIjMzM9VhEHOMmKQOdcSgLB0dlmWxcOFCjI+PpzoUIk2ZjntRpY5FXhI8PCqVCv39/akOg0gj4nUu5ua3tJJwz4nJLF26FJ2dnakOg0gz4vFtSufUwRUKyyR2eEpLS3H27NlUh0GkEeG8itWzkFJH2jh4h8LdHYjQ3HnnnTh9+nSqwyDSCKlTsSTO4NemNaJMqCQjI4OkjoJer8drr70W850oCUJwKiMjI2A5ViJKHakZECw29fCGpqCgAE888QR27qRRVER0xsfHowodLXvHnKkFeaUVS3c8NDQ0tejnEPv27UN7ezseffRRXLhwIdXhELOYoaGhSQlTQOpcJBie53lhQfJUzLzSv+Pj47h27RquXbuG8fFxjI6O4tq1a+LfvLw8LFq0KKYdzzWuXr2Ke++9F1lZWWAYBm+++WbA63v27MHu3buj1tNxiE514qVkOx+9UJIZHx/H0NAQBgYGkJmZiaysLPFvRkaGOJApIyND9Cv4L/B1Zg8ntfRG5DzPi1JLxRYegtTS50I56XbCAUJa71zD7/dDoVCkOgwiSUhn6QAgSik8BFGlIgc/DxZa2pcV3DxnGCb6r7QYhhHlk1aSkZEhyp6ZmSlKGmpYpFA+FqnlLvqiRYtSHQKRIMKN/grXuSwVWiptZmam6EywwJH2JRDzTy+lUkpP1AW5pTILAYyPj4vbCfJLxQ6H3MUm5Ecsl5ykzeXgbB0qI4e6rBXLqW2A1MFZGZgQTLpeqFRYDm6mS+u6du1agPjSMqEyNclMpDuRrhQFN5mDm9/Bsgc/gvcRLnvHlKkFqYOll8oaaofSLC0tF+7yF0lNpDthLzMFXaKSZuNIcoeSNto160lSS8WVLgc3IQCIzevgHQpNb+Gam7TZLWwXDAlNyIVQ0km9CdcMD5ZaKn/wQK9IQ0gjZurgzCzILW3b8zw/Kb3FqykAAAguSURBVGBpdg6VpYM700hoQm5EElvqUKisHep5KJnDZeyQUkfK1tK/QpBCRpa+LsgtNNEBOo8m5haxnF9LBQ4lurSeWLI0MIXe7+ANpdICgR1nUulDnUeTyMRcQ+pPcMYO7jyTtoQjXZMOR1ipQ3WOhQsOCJQ5eDSaUDYWmUl4Il2JRbhgMcPJG0r8UPsKtc9p9X5LKxIystAEl74eXE76lyDmGqG8CPXDjXBCx9r7HTBMNBTBQ0fD/Q133kw93QQRvUc81Pm2dLupdJRFlRoILbb0eax/w9VJEHImlHzRpI0mcaRsHZPUQHixpcvRmtjUBE89//XBxEyV3/n70oTUf8k7CNtrf0LVpvuwRJmbkH2kI9GazlPp4Y67+S0lktih1qWbxJc8A/j1f76Ky74hLC0uhLH6n7CQZcXXr3AcLEf/gJuW3YiN9343hZFOn//6evrZ75QlRmoiNmK9PBW8Lq7e70iBhOosC95huA6z2coVP4cTf3bgf/z3/4Z8VR6cbR/h+J9aUfngBmRlzYOz7SO8d/ZDlK5aieGRq2n7m3EmY/LIQCK1RBM5XJlwTGuCPKncwTsMtS74tdlI/6UBFC5RIV+VBwC45Vsr8GHHpxj0fYl8VR60ZbdCW3YrnG0fYXjkakx1Ots+gu21NwAAy4oLUVP9EBYqWPR7BnD8VCvUNxbh5Jtv41+2Pgzv5cvo7evH8MgIBi77UFP9EK74Ofz6N8cw6Ju4q8y/bH0YNy0vhv20AyrlYmjLbgUwcUD67R/+iAfWrxXjF9+XZ0Cso/xWDZYWFyI7O0uML9Z9nu/uhavTDf06nbht5/nPAg56E+/zBhw/1YrN//SPWKiYaOXYTzvw1l+dkz6HSJ/X3XdpsX7tnWh5/Q3ccdu3cdPyYvH9/PW9NjywYS2ysuYF1P1I5QNod3Vi0z/eHbL+2UDEc+EY5I6FuGa9DJY7UhDB2X22MeDzYYkqV4xxfnY22AUL4Pdzk5o/sQwCGB0dw+joGMxPPy5++c68cxb6dTowDIP+S158+5Zv4d9+8r8m9t/mg6vzvNhSAIDzPb3i8vnuz3Hi9Bn885YKlNysxjtnP0T5rSXIypqHS54B3JC/BAVLlAExXPFzOHHqjFhHv2cA//c//h/Wf+8fxPcQ6z4L8pV49/0P4eeGsVDB4qsrfoBhMDo2BoZh0PdFP+5aXT7xGeGbz8jZ9hF8Q1+Jn8P57s/x2p/+gqqvDwYC57s/R6f7c7GcwM0rluFcVzdWqG8EAHzWdwE3FhcgOzsLzraPwDCM+BnaTzswcNkX8yCNVBHr9ezpMmOTzkc9eQ8xemY2PTwDlwO+jNnZWVics2hyWTAAE/39ZGdnQXfHbcjOnrh9UcnN6oDtCvJVKF21MqDesr8rQcESpbju70tXicsF+Soo8xaLzxkGolCurm6U3KyeFEPHJ+dRWKD6po4lSmz43l3fvM8p7HN+dhYYZqLfwc8NY+TqKNgF83HJM4DRsTHMXzAfeYuvn/gefP0+/dwwPuz4FOvX3il+DkuLC8EumI/LXw4FxHrddQsxPDIivifhsfzGIoxcvYqxsTGMjY2h94t+LL+xSKz7O2WlYtnv3fUdMd7Z/IjXpWjM6PzUwcHM5uZ2MEvyAntqR0dH4fsyvpspnu/+HC9Zfisu3/3d1VPa/oqfw7//56vo6f0CwETTFgAWKljkXL8I/Ze8yF+ihO/LIeQHZWmB4Pc13X1mZWXhZvUyeAd9Yr3K3BxxWSgTDLtgfkBTOCsrC/PnZ+PKFT8gOVXIV+Xhnru0MP+8GcuKb8A/b6nAQgWL3JyJO8UM+oZw5Yof8+dnI1+Vhyt+blLd6Ui8AocioZPOJyLgRMEwDC55B8WYR8euYXj4Kq67bmHA+xAyXLT31tX9Od45+yF+9uMnkJWVha7uz+H61B2QmaVH5eB6r/g5/Pb3f8TmhzaKX+Lfn3xT3EZbdis+6vgUYBgsvv56XLdw8n3Pgt8TAHgGLmOJMndSHLHsc/nSIrz97lkwGRPPAeCD9nO4OjqKkptvClnn8PBV+LlhMb7R0VFcHZn8uQLACvVSPGf63+jq/hx/+ONbeHjTBmRnZ2NpUSE+672AS97BgP0E1+3nhjE8fHVGsl06Q12gX3PLqhW40O9Bv2cAAPDxuS4U5qsmdTzFysCgD4uvXyRmL9en7iltf8XPAYCYiS5e8mJg8LL4em7OIgyPXMUHH7kCLk+dOHUGzve/7rS68QZ0dX8mvqd+zwDaPuqY9j4XKlgM+obwSVdPQBbt6b0w6XxeKF+Yr8Kp1ncwOjoKAPis7yK4kavIzVn09Tn+MXG/AtctVGB4eARXR8fE9/HJ+R6MjIyI+xHqFi7RAROX6/xcYF1zkYRm6nRioYLF3d/V4vlf/TsAoPzvSvDwpg3Trq/s1lX43Wtv4GlzIwDgnik2vfNVefj2Ld/Cs883i/Hk5S4WX8/KysISZS4+Od8jyhWqjvvXrw14T2v/4TvT3qcgkvAcAG4sKsQn53uQnRX6q3T/+jU4ceoMfvJvB8U6H960YVJTvav7c7x0eOJUJTdnEf7nI5XiPoT3N39+YHN7w/fuDPiMtz78IC7HecokB6Y0+ISYXQgZWVt+a4ojmR30ewbw9rtn8eB93wt5fj9XoEwdJydOncGbb78XsO6e767G/evXJHS/V/wcPjnfg4c23pPQ/aQLo6OjONX6Dr5107I5LTRAmTotEQ4ktTWbsWL5jakOJ2UEH1CTcTBNB0hqgpAZ1PtNEDKDpCYImUFSE4TMIKkJQmaQ1AQhM/4/1GlLAuywdG4AAAAASUVORK5CYII=)
Go 中的数组
func main() {
// 初始化数组
var arr = [3] int {
1, 2, 3
}
// 查找元素
fmt.Printf("arr[1]: %d\n", arr[1])
// 删除元素
remove( & arr, 2)
// remove(&arr, 3) // will panic
fmt.Println(arr)
}
// 删除数组 arr 的某个元素
// index 为需要删除的索引
// 从需要删除的元素开始,依次将后面的元素往前移动一位即可
// 然后将最后一位修改为该类型的默认值
func remove(arr * [3] int, index int) {
if index >= len(arr) {
log.Panicf("%d remove out range arr", index)
}
for i: = index;
i < len(arr) - 1;
i++{
arr[i] = arr[i + 1]
}
arr[len(arr) - 1] = 0
}
Q: 为什么我们在 remove 函数当中的参数使用的是指针
这是因为在 go 中参数的传递都是值传递,如果不用指针的话,那么就会复制一份数据到函数中,这样就无法做到删除的作用
// 在函数 main 中
fmt.Printf("main: %p --> %+v\n", & arr, arr)
p(arr)
p2( & arr)
func p(arr[3] int) {
fmt.Printf("p: %p --> %+v\n", & arr, arr)
}
func p2(arr * [3] int) {
fmt.Printf("p2: %p --> %+v\n", arr, arr)
}
输出:
main: 0xc0000c2000-- > [1 2 0]
p: 0xc0000c2080-- > [1 2 0]
p2: 0xc0000c2000-- > & [1 2 0]
通过上面的例子我们就可以发现,在函数 p 中我们直接传递的数组,最后打印的变量地址是和 main 中不同的,就印证了我们之前的说法
在实际使用过程中,我们其实是很少使用到固定长度的数组的,而是使用可以自动扩容的 slice,接下来我们就深入的看一下 slice 当中的一些细节
深入理解 Slice
使用
基础使用
// 初始化
s1: = make([] int, 2)
fmt.Printf("s1(%p): %v, len: %d, cap: %d\n", & s1, s1, len(s1), cap(s1))
// s1(0xc00000c080): [0 0], len: 2, cap: 2
// 赋值
s1[0] = 1
s1[1] = 2
fmt.Printf("s1(%p): %v, len: %d, cap: %d\n", & s1, s1, len(s1), cap(s1))
// s1(0xc00000c080): [1 2], len: 2, cap: 2
// 扩容
s1 = append(s1, 3)
fmt.Printf("s1(%p): %v, len: %d, cap: %d\n", & s1, s1, len(s1), cap(s1))
// s1(0xc00000c080): [1 2 3], len: 3, cap: 4
// 删除元素
s1 = append(s1[: 1], s1[2: ]...)
fmt.Printf("s1(%p): %v, len: %d, cap: %d\n", & s1, s1, len(s1), cap(s1))
// s1(0xc00000c080): [1 3], len: 2, cap: 4
1.可以发现,通过 append 之后 s1 的容量和长度都发生了变化,说明完成了自动扩容
2.删除元素之后我们的长度发生了变化,但是容量还是原本不变
常见坑
// 复制一个 slice
s2: = s1[: 2]
fmt.Printf("s2(%p): %v, len: %d, cap: %d\n", & s2, s2, len(s2), cap(s2))
// s2(0xc00000c120): [1 3], len: 2, cap: 4
s1[0] = 10 // 这里可以发现,s1[0] s2[0] 都被修改为了 10
fmt.Printf("s1(%p): %v, len: %d, cap: %d\n", & s1, s1, len(s1), cap(s1))
// s1(0xc00000c080): [10 3], len: 2, cap: 4
fmt.Printf("s2(%p): %v, len: %d, cap: %d\n", & s2, s2, len(s2), cap(s2))
// s2(0xc00000c120): [10 3], len: 2, cap: 4
s1 = append(s1, 5, 6, 7, 8)
s1[0] = 11 // 这里可以发现,s1[0] 被修改为了 11, s2[0] 还是10
fmt.Printf("s1(%p): %v, len: %d, cap: %d\n", & s1, s1, len(s1), cap(s1))
// s1(0xc00011c020): [11 3 5 6 7 8], len: 6, cap: 8
fmt.Printf("s2(%p): %v, len: %d, cap: %d\n", & s2, s2, len(s2), cap(s2))
// s2(0xc00011c0c0): [10 3], len: 2, cap: 4
这是一个常见的例子,我们从 s1 复制了一个 s2
修改 s1 的第一个元素之后,s2 的一个元素也被修改了
但是我们触发了 s1 的自动扩容之后,s2 的第一个元素就不会随着 s1 的修改而变化了
这也是当函数的参数是 slice 时我们不允许直接修改,如果需要修改需要返回这个 slice 的原因,因为函数的参数也是值的复制
func sliceChange(s[] int) {
// 不允许直接这么操作
s[0] = 1
}
结构
大家如果使用过一段时间 golang 应该知道 slice 的底层结构其实是一个 struct
https://github.com/golang/go/blob/go1.15/src/runtime/slice.go
type slice struct {
array unsafe.Pointer
len int
cap int
}
![](data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAf8AAADxCAYAAADFjL56AAAebElEQVR4nO3df3BU9f3v8dcmQdjMVFqT8gXyFVL81qTcdhb9hlvakPEO1psoTO8VFJSYmf6gTUa+1iKi1TZhJIqllPL126tD/GLtNMQKFRy/X/mR2mauJmnTSdTu1NEErxjgBijNoshtNjHJnvsHc45nN7ubTbLJJvk8HzNnkj179nPOxnFen8/78zkHj2VZlsbZBJwCAACjeDyeUX82I4nX4SDsAQAYX5FZO5LOQFLDn9AHACA17AxOpBOQlPAfaejTSQAAYGQSHdkn0gnwjGXOP5GPRh5D8AMAMDqRgZ5IhyDaMaMK/+E+YllW1GMIfgAAxiZqmHs8w3YE3O+POPzjHR4KhRI+NpH3AQAw3UhCXZLS0tKGPXZE4R9rND9caT+yUzBcmwAAIH7wR4Z8tCmBmFWCRMM/2mGxRvrDdQjcxwEAgNic0bq7bB8n6BOpBCQU/sMFf6zQt4+JFvYEPwAAiYkW/PZPd7jH6gREdgBGdatfZPBHhr/92h3+Iw1+OgcAAFOMdNV+tJJ+rBK/dDmP3R2AYcN/uPL9cJt90sjPRGsbAACEc4/ko43mLcty3nNvkZ+3j5NGOPKPNcq3t1AoJMuy9FHb93Tp/f0KDfx9DF8Xk1X+BjptADCZ9Pf36+OPP5bH44k+x+/xhD38J+6cf7RRvvv3yNC3g3/etXcn+3thkmg/XED4A8Ak9PHHH6u/v98Z+aelpUWtBng8HsW+GTAOdyfAHfyhUEiX3t+fvG8CAAAScsUVVwzJ5FjT7DHDP9Zcf7zR/+DgIKV+AABSZHBwMKwDEG2dnWVZic35D7fIzwn+OA/zAQAA48udw2lpaUPutou74C+RUX8oFBqyDQ4OJvdbAACAhNk5HO1BP/aivxHP+cd6cp+7MwAAAFLDzuJ4eS2N4D7/yNJ/5Kjf3gcAAFLDfpiPncfRnhFgWdbwI/94PQf3yRj5AwCQWrHyODK7h4R/vKfuRa70jxz1E/4AAKROtFyOtuI/4Tn/eLf6UfYHACD13Hkc71a/uOGfyDP43c/v51n9AACkjnsgHi+TR/yEv2i9iFgrCwEAwMRxV+Tt1+79toRG/tFeRzsB4Q8AQOpE/ou6kdk84jn/WI3bJ3A3CgAAJp47+N37En62/3ANx/sdAACkRiI5PeLV/vHeZ7U/AACpk8ji+4Qe8hP5gUT2AQCA1IqX2aOa8wcAAFNXUsKf0T8AAJPHcLmctJE/HQAAAFIvkTym7A8AgGFGHf6M9AEAmPyi5XVSR/50CAAASJ1Ec3jal/2bW/0qWX+PAh9cHJf26w4dVfXuvc7vFQ9uV7C3L+HPd7x3Uruffi5qewAAjIdpH/7jqeO9k3r5lUbd/Y3bJUmlq2/Wnh0PyztrZkKfD/b2affTdfp/f+9x9q2+ZYW6zp1Xc6t/XK4ZAADCf5Ts4F51U5GyPjM7ae16Z81U2W0rVfvC4RFVEAAASJSR4V936Kg88wuczT3KDvb2qeLB7Xp63yFVPLjdOSaynH+q65zeP3VGBb7FYe3axwU+uKiS9ffopfpXVbL+Hqcdu6Qf+OCibv3W/aqpPaSqnXvCpiby/ylXnafP6o2/tE/QXwQAYBLjwr/u0FHtfKpW7Y0HZZ1pU3vjQW18aIfqDh0NO678ge0qu22lc0zL62/p0JEG5/02/9v63IL5WpAzN+75tu6s0RPV98s606aml55R1c49am71K+szs/XiL36q8rLV2ralQsee+7lTQcj6zGwVLvWpoak1+X8AAIDxjAr/wAcXVfvCEW25u0x51yyUJOVds1Bb7i5T7QtHwhYFbttSocKlPueYNStXqPFPbyrY26dgb58a//SmcubOGXZ+332u67+Ur/Ky1QmF+qKFOeo6d57SPwAg6YwK//b/06lz5wNhpXpJKvAtlmVZ6r7wobNv0cKcmO30BHvVefps3GNsuVfPH9W15l49X52nz6on2DuqzwMAEEtGqi9govnfPq78ojVD9vsWX5uCq4nv3PmAui98mNQFhQAAGBf+vsXXan/N404pPtJkKrPPnZOl7Ks+nerLAABMM0aV/e0gdZf3pZE/CCjTO0u5V8/TiZNdSb9GW+fpM8q9ep4yvbPG7RwAADMZFf724r6ND+1Qx3snJV1eBFi9e6/Kbrsl4fK6d9ZMFX35unFdkHfiZFdCCwoBABgpo8JfuvwUvi13lym/aI088wuU/V9uVNltt6h09c0jaqfAt1jvnzqjU13nRn0t9gN9qnbu0ZKvrQ/rkDS3+rVi+dJRtw0AQCweK+JfAXC/DIVCzr5QKBS2DQwMaHBwUAMDA+rv73e20Gt5yl/ZNrHfIgWCvX3atHWXir583Yg7DsNpbvWr9oXD2v3I5kk38m8/XKD8DfwDTgAwGR0/flwzZsxwtoyMDKWnpysjI0NpaWmfbKm+0KnKO2umNn23VC+/0pjUfzQo2Nun2hcOq+y2lZMu+AEA0wPhPwZ51yzUqpuK9NQvf5O0Ng8daVDO3DnOA4YAAEg24271S7Zkl/yT3R4AAJEY+QMAYBjCHwAAwxD+AAAYhvAHAMAwhD8AAIYh/AEAMAzhDwCAYQh/AAAMQ/gDAGAYwh8AAMMQ/gAAGIbwBwDAMIQ/AACGIfwBADAM4Q8AgGEIfwAADEP4AwBgGMIfAADDEP4AABiG8AcAwDAZyW7Qylmrd/78k2Q3i8kiZ22qrwDj6J2j61J9CQDGIP2a6oSOS3r4S9IXlj8wHs1iEniniY7ddGfS/7/vNP2E7zuNmfh9E0XZHwAAwxD+AAAYhvAHAMAwhD8AAIYh/AEAMAzhDwCAYQh/AAAMQ/gDAGAYwh8AAMMQ/gAAGIbwBwDAMIQ/AACGIfwBADAM4Q8AgGEIfwAADEP4AwBgGMIfAADDEP4AABiG8AcAwDCEPwAAhiH8AQAwDOEPAIBhCP84Ahcu6s5vPayOd08mrc3mFr9Kbr1HgQsXR3Qd1Tv2KhjsG9O5x+P7AACmHsI/jqf+/TdaVVKkvM8vTFqbhct8Ovbiz5V11ewRXUfX2fNjPnfWVbP1L99dp91P1o25IwEAmLoI/xiaW/yXR+lf+2qqLyWprvflS5Le8Len+EqQCrt27dKlS5dSfRkAUmzShH/1jr3yXFngbBXf3+6MToPBPlV8f7uefvaQlhSul+fKAjW3+FV34KgeqPw3VXx/uzxXFqh6x15JUse7J53j7K25xS/pcum75NZ7VHfgaNj5m1v8WlK43imJN7zaqsJlPmeE3vHuSRX/z3/RS4dfDWvbbjfed3Ef4y77u7+X/R3c391+v+qxPar5xSF95WvfdK7P/h7R/l6SYv5tvN6ZKvrqdap9/jCjfwP96Ec/UlZWlh566CE6AYDBJkX4V+/Yq66z59Xz12ZZH7Wpu/P36jx5Vj/9t9qw457a+4L2//JxWR+1qXCZT5K084lfqeir18n6qE2VD25Qx7snte4bD+nJXQ/K+qhN1kdt2re3Whs371DHuyeVddVsFS7zqfEPb4aFX8OrrVq29Ita8I9zFbhwUc0tfq24YWnY+f/6twvaur3GuYam3z6j5f/9206422Hd3OJXd+fvox4TTfm921V2x0pZH7Wp/fWDaml9S4f+s0Fe70zt+deHte2HFSr/1mr98XfPKu/zCxW4cFGl3/6RCpf5nO+YM2+Obl1/f9hagsi/ja3gusV6v/OMTv3fc6P/j4Yp6cc//rHS09P1s5/9TJ/97GfpBACGSnn420FbdsdKeb0zJckJ6K6z58MCes3XVwyZfy++8Sthpfm2N9/WsqVfdMrb0uWwk6TuwIeSpBU3LFVL61tO+NnXUPTV6+T1zlT78U6dOx9Qdtanh1zvlnvLnGsoXObTth9WOKPoN/ztaml9S0/85H6nYhB5TDTbfljhdGbyPr9Qa76+YkjnxO3Y7/4gSbr7O7c7++zf7fei/W1s2Vmflsfjcf4eMMe9996rzMxMffzxx+rr66MTABgq5eGfddVsHXvx5ypc5gsrZVc9tmfIsYs+lzNkX+7Cecr0znJel669WXv+9WF5vTNVd+CoPFcWKP+f18j/l+POMfnX5mrunCy1vfm2JDlhb3cSOk+d0dw5WUPC/x8+e5VzjG3FDUvVefKseoK9MT8X2dlI5HvFEgz2qfEPb4ZNSUifdJhOvN8V829jy/TOUu7Ceeo8dSbh87p5PB55PB498sgjzr5HHnmE/VNk/w033OC8b3cCdu3apW9+85sCYIaUh7/0yRx5du6Nyl04Tz1/bda2H1aMqi33fP9dGyrV9Ntn1P76Qfm+dK1zTNZVs1V25y3O6Npd8h+rWIGbbFWP7QlbVxCrwxSPu6MwEpZlybIsbd261dm3detW9k+R/a+99prz/hVXXKGZM2dq8+bNevbZZwXADBmpvoCOd0/q4H80qOm3zzil77E4cOgVLVv6Rf3xd8860wjR7msvuG6xfvXcYb3hb7887XDnLc7xIxE5erarAJFt2RWBZJXat/2wImwefzRGUnHA9PDEE0+op6dHV1xxhTwejzZt2qSHH35Yn/rUp1J9aQAmUMpH/t2BDzV3Tpbyr8119tlz8CMVDPap6+x5Z+7e1vbm22Flf0la8I9z9bnc+Xrp8KuyLCusnJ+7YL7OnQ8MCeq//u2CM1VgO/F+l1OCj/W5hldbk1YR8HpnKmfenCHrIezFhpF3MUTTE+xV58mzyl0wf8zXg6nlBz/4gQYGBnTffffpb3/7mx5//HGCHzBQysM/O+vTOnc+ELZQ7al//43qf/9HZxSdKDsYa399xFn13vHuSe184vJdA+5Run3L284nfqXP5c4PK/nbawKijdJ3PlHrVBKaW/w6+B8NWrv6JkmX76FftvSLuveBnzrnb27xq+qxPWELGsfq7u/cPuRuiEP/2aDOk2cTei5Bd+BDWZYVdUEjprdHH31UgUCA0AcMl/Lwz/v8Qj2560HdtaHSmbuWpH17q6OOoodz//fKlLtwnrJzb5TnygLntr/iG78yZI674LrF8n3p2iGVAnvxXMOrrUPav3vDbVr3jYfkubJAGzfv0P5fPu6s/rdvzStc5nPOv3HzDrW/fnBMUxprV9+klta3lPkPhWpu8Svrqtmqe+ZRNbf4nb9Z7a+PqO6ZRxN6cmDbm28P6fDADJs3byb0AchjWZbl3uF+GQqFnH2hUChsGxgY0ODgoAYGBtTf3+9sg+9V6gvLH5jYbzFKzS3+IQHufq96x14nUN3PD0jG2oRUCQb7tOmhXSq7Y+Wovsc7TT/RF27ePw5XhsngnaPrpsz/v8nwTtNP+L7TmInfN/2aas2YMcPZMjIylJ6eroyMDKWlpX2ypfpiU6nh1daozw6QLt+fX7jMFzYdMR3Yj/V1PwcBAGAWI8Pfvv+/6+x53f+9spjH3f2d2/XyscZp86/gBS5c1P96er82bSxN2voDAMDUk/Jb/VKhdO3NKl1787DHZV01W7/+xXbn9Z+bnxvPyxp3kd8HAGAmI0f+AACYjPAHAMAwhD8AAIYh/AEAMAzhDwCAYQh/AAAMQ/gDAGAYwh8AAMMQ/gAAGIbwBwDAMIQ/AACGIfwBADAM4Q8AgGEIfwAADEP4AwBgGMIfAADDEP4AABiG8AcAwDCEPwAAhiH8AQAwjMeyLMu9w/0yFAo5+0KhUNg2MDCgwcFBDQwMqL+/39lCr+VN7DfAhMvfYA1/EKakd46uS/UlABiD9GuqNWPGDGfLyMhQenq6MjIylJaW5mwZ43Hy/JVt49EsJoH2wwWpvgSMoy/cvD/VlwBgDI4fP57QcZT9AQAwDOEPAIBhCH8AAAxD+AMAYBjCHwAAwxD+AAAYhvAHAMAwhD8AAIYh/AEAMAzhDwCAYQh/AAAMQ/gDAGAYwh8AAMMQ/gAAGIbwBwDAMIQ/AACGIfwBADAM4Q8AgGEIfwAADEP4AwBgGMIfAADDEP4AABiG8E+SukNHVb17rySpudWvkvX3KPDBxYQ/H/jgoqp371Wwt29IewBQXV0tj8cjj8ejiooKBYPBVF8SpjDCPwk63jupl19p1N3fuF2SVLjUp2PP/VxZn5mdcBtP/fI36jp33nm9+pYV6jp3Xs2t/qRfL4CpJRAIqLm52Xnd0tKiU6dOpfCKMNUR/mMU7O3T7qfrtOqmohGF/XC8s2aq7LaVqn3hsFMNAGCm9vZ21dfX64477tAdd9whv9+vtra2VF8WprBpHf4d753Ukq+tl2d+gTzzC1Tx4PawIG1u9TvveeYXaMnX1qvjvZPO+9W79zpbrDZOdZ3T+6fOqMC3OKxdu+wf7O1TxYPb9fS+Q6p4cPuQduz3q3buUU3tIX1l1Teda8j/p1x1nj6rN/7SPgF/LQCTVUNDgyRp1apVWrVqlSSpsbFxSOnfnhqoqKhQSUmJPB6PqqurVVdXJ4/HozvvvFN33nln2NRBR0eHlixZ4kwpeDwep8pgfy5ymsH+TElJiQKBwAT9FZBM0zb8m1v9yi9aoycff1DWmTZZZ9qUM3eONm3dpWBvn5pb/dr40A61Nx503l+zcoXurfxp2Fx91c49kiTrTJt6Tlz+H8JuQ5La/G/rcwvma0HO3LjXU/7AdpXdtlLWmTa1Nx5Uy+tv6dCRBnlnzdSeHQ9r25YKlZet1h9fflZ51yyUJGV9ZrYKl/rU0NQ6Hn8iAFOAXfL3+XwqKChQQUGBfD5f3NJ/TU2N6uvrJUmLFi1y9j///PN6/vnnJUk5OTk6deqU1q1bJ78/fHpx48aN6ujoUElJiYqLi4ecq62tTX6/X4WFhcrKykr2V8YEmLbh39DUqm1bKlS41Ofsq9y0QXt2PCzvrJlqaGrVmpUrnKCVpBXLl+rc+YC6L3zo7Cv+b19x5vK9s2Zq03dL1fL6W3rjL+0K9vap8U9vKmfuHHlnzYx7Pe5rybtmodasXKHGP705bEl/0cIcdZ07T+kfMJRd8p87d66ys7O1YMECLVu2LG7p3+fzqb29XZZlqbS0NOy9pqYmWZalyspKJ8T37dsny7LU3d2t4uJi+f1+dXd3KysrS4WFhWHnCgaDamxslM/n09q1a8f9+2N8TMvwD3xwUc2tfi1amBPzmMpNG1S5aYMkOWX95f/j20OOK1zqC5vLX5AzV8v++YvqPH1GPcFedZ4+G/c8tkSOiSb36vnqPH1WPcHeUX0ewNRml/ztUbbX61VRUZGk6KV/SVqzZo3y8vKG7C8vL9f111/vvC4tLXU6CNXV1crOznYqBrYVK1aEnevUqVNqaWnRsmXLtGDBgqR9T0ysaRn+ttyr58d8zz3ff/Bwg9obD6rppWcm8OoSF1mNAGAG9yr/qqoqZ07+rrvukjT2Vf/Nzc1Om1VVVVGPyc/PDyv9HzhwQH6/X0VFRfJ6vaM+N1JrWod/5+kzUfcHe/tU+8JhbdtSIetMm/78u+fCyv/x2KP9iTR3Tpayr/r0hJ4TQOrZJf9Y/H6/Dhw4MKq2g8GgamtrJV2uCPT09Dhlfzd36f/IkSNh6w8wdU3L8M/0zlLu1fN04mRX1PftAF+xfGnY/mgL65pb/WELALsvfCjLslTgWzzseZKh8/QZ5V49T5neWeN2DgCTk13y37ZtmyzLCtv27dsn6fLofTQr7nt6etTZ2SlJKisrk9frjdnZsEv/9913n+rr62NOK2DqmJbhb98jX7VzT9hDcuoOHVXJ+nvU29un3Kvnhd1D39zqV9XOPfK/fTysxF7/v/+op375G0mf3NO//L8uUd41C+WdNVNFX75uXBfknTjZldCCQgDTi7vkb4evm73qv76+Xu3tI78dODMzU7m5uZKk5cuXy+PxaPny5VGPvf7661VeXu68jnY9mFqmZfhLlxfqtTce1MaHdjhz+7UvHFHdk48qZ94cPfaDjeo8fVaZiwrlmV+g6t171fTSM/ItvjZsuqC8bLUu/b1HnvkFylxUqJy5c5yFgpJU4Fus90+d0amuc2O63rVfv0ktr7+lzEWFTofFXrgYWaEAMP3Zo3Cfz6fs7Owh79ur/qVPKgQj4fV69dhjj4WV+ZuampyKgrtN9yLD4uJi5efnj/h8mFw8lmVZ7h3ul6FQyNkXCoXCtoGBAQ0ODmpgYED9/f3OFnotT/krp8eTp6p371XXufPa/cjmmCPvYG+fNm3dpaIvX6fS1Tcn9fzNrX7VvnA47vknWvvhAuVvsIY/EMC0Ul1draqqKm3btk2VlZWpvhzEcPz4cc2YMcPZMjIylJ6eroyMDKWlpX2ypfpCpzr73v+XX2kc0T/kMxx7UWLZbSsnTfADMEswGFRFRYVzNwD39k8fhH8S5F2zUKtuKnLWBiTDoSMNypk7J+whRQAwkbxer3JyPnlGyZNPPslCv2mCsj9GhLI/AExelP0BAEBUhD8AAIYh/AEAMAzhDwCAYQh/AAAMQ/gDAGAYwh8AAMMQ/gAAGIbwBwDAMIQ/AACGIfwBADAM4Q8AgGEIfwAADEP4AwBgGMIfAADDEP4AABiG8AcAwDCEPwAAhiH8AQAwDOEPAIBhMsaj0fbDBePRLAAASIKkh3/+BivZTQIAgCSi7A8AgGEIfwAADEP4AwBgGMIfAADDEP4AABiG8AcAwDCEPwAAhiH8AQAwDOEPAIBhCH8AAAxD+AMAYBjCHwAAwxD+AAAYhvAHAMAwhD8AAIYh/AEAMAzhDwCAYQh/AAAMQ/gDAGAYwh8AAMMQ/gAAGIbwBwDAMIT/MOrq6uTxeFRRUaFgMKhAIKCSkhJ5PB41Nzen+vIAABgxwh8AAMNkJLMxj8eTzOYmpaysLB07dizVlwEAwBCJ5vCoR/7TJeg7Ojq0ZMkSeTweeTweLVmyRB0dHTGPj1X2DwaDqqioiNuO+7PuqQQAAMZLtLw2uuzf0dGhdevWye/3O/v8fr/WrVsXtwMQKRAI6NZbb1VNTU3Mdjo6OnTjjTeqvr7eOaampka33nqrAoFAEr4NAACJSVr4T8VKQHd3t/x+v8rLy9XT06Oenh6Vl5fL7/erra0t4XaOHTum+vp6FRcXq7u7W5Zladu2bfL7/Tpw4IAk6cCBA/L7/dq3b58sy3KOqa+vZxoBAJA0ieRxUsJ/Kga/JGVnZ8vn86mmpkaZmZnatGmTdu/eLcuyVFpamnA7J06ckCSVlZUpKytLklRZWSnLslRZWalAIOBMEdx1111O2b+qqirs8wAAJMNwuWx02T8vL09btmxxXtudgJHcxhcMBtXV1TWm6+jq6mLuHwAwYUYU/tF6ElN11G8rLS11yvBNTU3O/tra2oQC2ev1KicnJ+HzNTU1Oeeztz179sjr9Y7q+gEAiCZeZicc/omE/FTrCEQ+wKewsNDpAHR2dqqnpyehdhYtWiTpcofBXrznbjszM1OFhYXOMcFgMOzugLq6unH4dgAA0ySa1SO+z9/dcKzfp4qSkhIVFxerpqYmbKW+JBUWFjrz94m2U19fr+zs7LD3ysrK5PV6tXbtWh08eHDIuYqLi1VSUjL2LwMAgBLL6VHN+UcGvf16qnUAsrKyVFdXp+Li4rD9+/btU2Vl5YjaefHFF1VeXh62v6mpyRnx5+Xlaf/+/fL5fM77xcXFqqurS7iTAQBAPLHyeMhry7Is9w73y8i56VAo5GyDg4MaGBjQ4OCg+vv7NTAwoIGBAacEDgAAJtaJEyeUkZGhjIwMzZgxQ+np6crIyFB6errS0tI+2UZ7Avt2NUlKS0sLew0AACaencVpaWlhryMlFP7xygiRHYBQKDSmCwcAACMXCoWGDf4Rr/a32SHvbsh9okuXLo36wgEAwOhcunRpyIDc5s5qKUr4x1vB764ARJYW7BNduHBBFy9epAIAAMAECIVCunjxoi5cuBA1l90VAPvnsLf6eTweWZbl/HTvd/cwLMtyfgYCAZ07d06Dg4PO4kD3YkG7Y+BeTAgAAD4RGdxhC/bS0pxFfOnp6c7iPvf77jYi2034Pn93+EeO/O07AdLT050wT09Pj9pGWlpaQuFPhwAAYIpYT+OLtbjeHfzu0E9PT3eyNtrI3253xA/5cYe3u4xgdwLcoW+fMBQKOZ+zOwnuDkAsdAAAANNdvDvl3MFv/4wc/bs3d+i7Px855x81/CNH+ZKGlP7tRuzXkc8EcLc1ODgY1kFwHxNt5E/oAwBME++OOvcI3s5T9+g/slMQuUWeY0Qj/2jz/5GhHnkCd6k/FAqFHRdrUSDhDwAwTawKQOT8vXt0H68TEG0B/7DhH22Bnx387ouR5JT1I09gl/ztew/d5X77c5EIfgCAqaI+kMd9i16M8n9k+Ls7CZEP4kt4zj9ypG93AtxzCPZqf/cFukf70Ub9kYsCCX4AgOnidQDc2RutChDt92gP6osb/vFG/+6f9kXZI3z3+3YnwJ4akJjnBwAgnkTm/91BH61D4G4n8uf/B1DVuenVvrEWAAAAAElFTkSuQmCC)
如图所示我们可以发现,slice 的底层结构是一个结构体:
1.它包含了一个指向一个数组的指针,数据实际上存储在这个指针指向的数组上
2.len 表示当前 slice 使用到的长度
3.cap 表示当前 slice 的容量,同时也是底层数组 array 的长度
这也就回答了我们上面的发现的现象,在复制 slice 的时候,slice 中数组的指针也被复制了,在出发扩容逻辑之前,两个 slice 指向的是相同的数组,出发扩容逻辑之后指向的就是不同的数组了
同时因为结构体中 array 是一个指针所以在 slice 作为参数传递的时候,这个指针也会被复制一份,所以也会有相同的问题
创建
// 创建一个 slice
// et: 数据的类型
// len: slice 长度
// cap: slice 容量
// 返回一个指针
func makeslice(et * _type, len, cap int) unsafe.Pointer {
// 通过 cap 计算当前类型的 slice 需要的内存容量以及是否超出最大容量
mem, overflow: = math.MulUintptr(et.size, uintptr(cap))
// 异常情况判断
if overflow || mem > maxAlloc || len < 0 || len > cap {
// 通过 len 计算当前类型的 slice 需要的内存容量以及是否超出最大容量
// 如果是 len 超过限制则抛出 len 的相关异常,否则抛出 cap 异常
mem, overflow: = math.MulUintptr(et.size, uintptr(len))
if overflow || mem > maxAlloc || len < 0 {
panicmakeslicelen()
}
panicmakeslicecap()
}
return mallocgc(mem, et, true)
}
还有一个 64 位的:
64 位对比默认的只是进行了一下数据格式转换,但是这个转换的对比还是很有意思的
如果是在 64 位的机器上,那么 int == int64 的
如果是在 32 位的机器上,那么 int == int32,如果 int64(int(len64)) != len64,那么就说明这个长度超出了当前机器的内存位数,直接抛出异常错误就好了
func makeslice64(et * _type, len64, cap64 int64) unsafe.Pointer {
len: = int(len64)
if int64(len) != len64 {
panicmakeslicelen()
}
cap: = int(cap64)
if int64(cap) != cap64 {
panicmakeslicecap()
}
return makeslice(et, len, cap)
}
扩容
// 当 append 需要扩容的时候会调用这个函数
// et 是当前 slice 的类型
// old 是原有的 slice
// cap 是满足扩容所需的最小容量
func growslice(et * _type, old slice, cap int) slice {
// ... 一些校验逻辑,略过
// 下面这个就是扩容算法
newcap: = old.cap
doublecap: = newcap + newcap
if cap > doublecap {
newcap = cap
} else {
if old.len < 1024 {
newcap = doublecap
} else {
// Check 0 < newcap to detect overflow
// and prevent an infinite loop.
for 0 < newcap && newcap < cap {
newcap += newcap / 4
}
// Set newcap to the requested cap when
// the newcap calculation overflowed.
if newcap <= 0 {
newcap = cap
}
}
}
// 下面去计算新的数组所需要的内存
// 通过 old.len, cap, 以及 newcap 计算
var overflow bool
var lenmem, newlenmem, capmem uintptr
// Specialize for common values of et.size.
// For 1 we don't need any division/multiplication.
// For sys.PtrSize, compiler will optimize division/multiplication into a shift by a constant.
// For powers of 2, use a variable shift.
switch {
case et.size == 1:
lenmem = uintptr(old.len)
newlenmem = uintptr(cap)
capmem = roundupsize(uintptr(newcap))
overflow = uintptr(newcap) > maxAlloc
newcap = int(capmem)
// ... 有好几个分支,看一个类似的就可以了
}
// 检查是不是超过内存限制
if overflow || capmem > maxAlloc {
panic(errorString("growslice: cap out of range"))
}
// 分配内存
var p unsafe.Pointer
if et.ptrdata == 0 {
p = mallocgc(capmem, nil, false)
// The append() that calls growslice is going to overwrite from old.len to cap (which will be the new length).
// Only clear the part that will not be overwritten.
memclrNoHeapPointers(add(p, newlenmem), capmem - newlenmem)
} else {
// Note: can't use rawmem (which avoids zeroing of memory), because then GC can scan uninitialized memory.
p = mallocgc(capmem, et, true)
if lenmem > 0 && writeBarrier.enabled {
// Only shade the pointers in old.array since we know the destination slice p
// only contains nil pointers because it has been cleared during alloc.
bulkBarrierPreWriteSrcOnly(uintptr(p), uintptr(old.array), lenmem - et.size + et.ptrdata)
}
}
// 将原本的数组复制到新数组上
memmove(p, old.array, lenmem)
return slice {
p, old.len, newcap
}
}
我们重点看一下扩容的算法,可以发现有三种逻辑:
1.如果需要的最小容量比两倍原有容量大,那么就取需要的容量
2.如果原有 slice 长度小于 1024 那么每次就扩容为原来的两倍
3.如果原 slice 大于等于 1024 那么每次扩容就扩为原来的 1.25 倍
newcap := old.cap
doublecap := newcap + newcap
if cap > doublecap {
newcap = cap
} else {
if old.len < 1024 {
newcap = doublecap
} else {
// Check 0 < newcap to detect overflow
// and prevent an infinite loop.
for 0 < newcap && newcap < cap {
newcap += newcap / 4
}
// Set newcap to the requested cap when
// the newcap calculation overflowed.
if newcap <= 0 {
newcap = cap
}
}
}
空 Slice
我们先看一下 Slice 初始化的方式
var s1 []int
s2 := make([]uint, 0)
s3 := []int{}
// fmt.Printf("%p: %v, len: %d, cap: %d\n", s1, s1, len(s1), cap(s1))
// 0x0: [], len: 0, cap: 0
// 0x587450: [], len: 0, cap: 0
// 0x587450: [], len: 0, cap: 0
tips: %p 打印 slice 会打印 slice 底层指向的数组的地址
我们可以发现,第一种方式进行初始化,出现的也就是 slice 的零值,底层的数组指针是一个 nil
第二种和第三种的底层指针都有一个值,不过没有实际分配内存
这三种方式初始化出来的 cap、和 len 的长度都是 0
规范技巧
1.slice 作为参数时,不要直接存储它的引用,而是通过 copy 复制一份
原因请查看上文,Slice 的结构
示例:Uber Go 规范: nil-是一个有效的-slice
2.要检查切片是否为空,请始终使用 len(s) == 0 。而非 nil 。
原因请查看上文,Slice 初始化
示例:Uber Go 规范: 在边界处拷贝-Slices-和-Maps