从Chrome源码看JS Array的实现

时间：2021-10-17 23:36:40

.aligncenter { clear: both; display: block; margin-left: auto; margin-right: auto }
.crayon-line span::after { content: " " }
p { font-size: 15px; text-indent: 2em }
#colorbox.crayon-colorbox,#cboxOverlay.crayon-colorbox,.crayon-colorbox #cboxWrapper { position: absolute; top: 0; left: 0; z-index: 9999; overflow: hidden }
#cboxOverlay.crayon-colorbox { position: fixed; width: 100%; height: 100% }
.crayon-colorbox #cboxMiddleLeft,.crayon-colorbox #cboxBottomLeft { clear: left }
.crayon-colorbox #cboxContent { position: relative }
.crayon-colorbox #cboxLoadedContent { overflow: auto }
.crayon-colorbox #cboxTitle { display: none !important }
.crayon-colorbox #cboxLoadingOverlay,.crayon-colorbox #cboxLoadingGraphic { position: absolute; top: 0; left: 0; width: 100%; height: 100% }
.crayon-colorbox #cboxPrevious,.crayon-colorbox #cboxNext,.crayon-colorbox #cboxClose,.crayon-colorbox #cboxSlideshow { cursor: pointer }
.crayon-colorbox .cboxPhoto { float: left; margin: auto; border: 0; display: block; max-width: none }
.crayon-colorbox .cboxIframe { width: 100%; height: 100%; display: block; border: 0 }
#colorbox.crayon-colorbox,.crayon-colorbox #cboxContent,.crayon-colorbox #cboxLoadedContent { }
#cboxOverlay.crayon-colorbox { background: #000 }
#colorbox.crayon-colorbox { outline: 0 }
.crayon-colorbox #cboxContent { margin-top: 20px; background: #000 }
.crayon-colorbox .cboxIframe { background: #fff }
.crayon-colorbox #cboxError { padding: 50px; border: 1px solid #ccc }
.crayon-colorbox #cboxLoadedContent { border: 5px solid #000; background: #fff }
.crayon-colorbox #cboxTitle { position: absolute; top: -20px; left: 0; color: #ccc }
.crayon-colorbox #cboxCurrent { position: absolute; top: -20px; right: 0; color: #ccc }
.crayon-colorbox #cboxPrevious,.crayon-colorbox #cboxNext,.crayon-colorbox #cboxSlideshow,.crayon-colorbox #cboxClose { border: 0; padding: 0; margin: 0; overflow: visible; width: auto; background: 0 }
.crayon-colorbox #cboxPrevious:active,.crayon-colorbox #cboxNext:active,.crayon-colorbox #cboxSlideshow:active,.crayon-colorbox #cboxClose:active { outline: 0 }
.crayon-colorbox #cboxSlideshow { position: absolute; top: -20px; right: 90px; color: #fff }
.crayon-colorbox #cboxContent { margin-top: 0 }
.crayon-colorbox #cboxLoadedContent { border: 0 }
#crayon-main-wrap .form-table th { width: 100px }
#crayon-log { display: none; max-height: 200px; border-color: #dfdfdf; background-color: white; border-width: 1px; border-style: solid; margin: 1px; padding: 3px; overflow: auto; white-space: pre; margin-bottom: 5px }
.crayon-span,.crayon-span-5,.crayon-span-10,.crayon-span-50,.crayon-span-100,.crayon-span-110 { line-height: 24px; display: inline-block }
.crayon-span-5 { min-width: 5px }
.crayon-span-10 { min-width: 10px }
.crayon-span-50 { min-width: 50px }
.crayon-span-100 { min-width: 100px }
.crayon-span-110 { min-width: 117px }
.crayon-span-margin { margin-left: 5px }
#height_mode,#width_mode { min-width: 65px }
.crayon-error { color: #F00 }
.crayon-success { color: #00F }
.crayon-warning { color: #ff8000 }
.crayon-help { min-height: 30px; padding: 5px 10px }
.crayon-help .crayon-help-close,.crayon-help .crayon-help-close:active,.crayon-help .crayon-help-close:hover { text-decoration: none; float: right; color: #000 }
.crayon-help span,.crayon-help a { margin: 0; padding: 0; font-size: 12px }
#crayon-log-text { font: 11px/13px Monaco, "MonacoRegular", "Courier New", monospace }
#crayon-log-controls { float: left; margin-right: 5px }
.crayon-table { font-size: 12px; border: 1px solid #999; padding: 0; margin: 0; margin-top: 12px }
.crayon-table td { vertical-align: top; border-bottom: 1px solid #AAA; padding: 0 6px; margin: 0; background: #EEE }
.crayon-table-light td { background: #f8f8f8 }
.crayon-table-header td { font-weight: bold; background: #CCC }
.crayon-table-last td,.crayon-table tr:last-child td { border: 0 }
#lang-info div { padding: 5px 0 }
.crayon-table .not-parsed { color: #F00 }
.crayon-table .parsed-with-errors { color: #f90 }
.crayon-table .successfully-parsed { color: #77a000 }
#crayon-live-preview,#crayon-log-wrapper { padding: 0; width: 100%; float: left; clear: both }
#crayon-live-preview { float: none; padding: 0 }
#crayon-logo { text-align: center }
#crayon-info,#crayon-info td { border: 0; padding: 0 5px; margin: 0 }
.crayon-admin-button { display: inline-block; text-align: center }
#crayon-subsection-langs-info { margin-top: 5px }
#crayon-theme-editor-admin-buttons { display: inline }
#crayon-theme-editor-admin-buttons .crayon-admin-button { margin-left: 5px }
#crayon-theme-info { display: table; padding: 0; margin: 0; margin-top: 5px }
#crayon-theme-info>div { display: table-cell; vertical-align: middle }
#crayon-theme-info .content * { float: left }
#crayon-theme-info .field { font-weight: bold }
#crayon-theme-info .field,#crayon-theme-info .value { margin-left: 5px }
#crayon-theme-info .description.value { font-style: italic; color: #999 }
#crayon-theme-info .type { text-align: center; min-width: 120px; font-weight: bold; border-right: 1px solid #ccc; padding-right: 5px }
#crayon-theme-info .type.stock { color: #666 }
#crayon-theme-info .type.user { color: #5b9a00 }
#crayon-editor-table td { vertical-align: top }
.small-icon { width: 24px; height: 24px; display: inline-block; margin: 5px 5px 0 0 }
#twitter-icon { background: url("../images/twitter.png") }
#gmail-icon { background: url("../images/google.png") }
#docs-icon { background: url("../images/docs.png") }
#git-icon { background: url("../images/github.png") }
#wp-icon { background: url("../images/wordpress-blue.png") }
#donate-icon { background: url("../images/donate.png"); width: 75px }
#crayon-donate,#crayon-donate input { margin: 0; display: inline; padding: 0 }
#crayon-theme-editor-info a { text-decoration: none !important; font-style: italic !important; color: #666 !important }
#crayon-main-wrap .form-table .note { font-style: italic; color: #999 }
#crayon-change-code-text { width: 400px; height: 300px }
.crayon-syntax { overflow: hidden !important; position: relative !important; text-align: left; direction: ltr !important }
.crayon-syntax div { background: 0; border: 0; padding: 0; margin: 0; text-align: left }
.crayon-syntax.crayon-loading { visibility: hidden }
.crayon-syntax,.crayon-syntax .crayon-main,.crayon-syntax .crayon-toolbar,.crayon-syntax .crayon-info,.crayon-syntax .crayon-plain,.crayon-syntax .crayon-code { width: 100% }
.crayon-syntax .crayon-main,.crayon-syntax .crayon-plain { overflow: auto }
.crayon-syntax,.crayon-syntax .crayon-main,.crayon-syntax .crayon-plain,.crayon-syntax .crayon-table { padding: 0; margin: 0 }
.crayon-syntax-inline { margin: 0 2px; padding: 0 2px }
.crayon-syntax .crayon-table { border: none !important; background: none !important; padding: 0 !important; margin-top: 0 !important; margin-right: 0 !important; margin-bottom: 0 !important; width: auto !important; border-spacing: 0 !important; border-collapse: collapse !important; table-layout: auto !important }
.crayon-syntax .crayon-table td,.crayon-syntax .crayon-table tr { padding: 0 !important; border: none !important; background: 0; vertical-align: top !important; margin: 0 !important }
.crayon-syntax .crayon-invisible { display: none !important }
.crayon-plain-tag { margin-bottom: 12px }
.crayon-popup .crayon-plain { display: block !important; width: 100% !important; height: 100% !important; opacity: 100 !important; position: relative !important }
.crayon-popup-window { background: #fff }
.crayon-syntax .crayon-num { text-align: center; padding: 0 5px; margin: 0 }
.crayon-syntax .crayon-toolbar { position: relative; overflow: hidden; z-index: 4 }
.crayon-syntax .crayon-info { position: absolute; overflow: hidden; display: none; z-index: 3; padding: 0; min-height: 18px; line-height: 18px }
.crayon-syntax .crayon-info div { padding: 2px !important; text-align: center }
.crayon-syntax .crayon-toolbar span { padding: 0 4px !important }
.crayon-syntax .crayon-toolbar .crayon-button { display: inline; float: left !important; position: relative; width: 24px; background-repeat: no-repeat; line-height: 15px; border: 0; text-decoration: none }
.crayon-toolbar .crayon-button,.crayon-toolbar .crayon-button:hover,.crayon-toolbar .crayon-button.crayon-pressed:hover { background-position: 0 center }
.crayon-toolbar .crayon-button.crayon-pressed,.crayon-toolbar .crayon-button:active,.crayon-toolbar .crayon-button.crayon-pressed:active { background-position: -24px 0 }
.crayon-toolbar .crayon-button.crayon-popup-button .crayon-button-icon,.crayon-toolbar .crayon-button.crayon-popup-button:hover .crayon-button-icon,.crayon-toolbar .crayon-button.crayon-popup-button.crayon-pressed:hover .crayon-button-icon { background-position: 0 0 }
.crayon-toolbar .crayon-button.crayon-copy-button .crayon-button-icon,.crayon-toolbar .crayon-button.crayon-copy-button:hover .crayon-button-icon,.crayon-toolbar .crayon-button.crayon-copy-button.crayon-pressed:hover .crayon-button-icon { background-position: 0 -16px }
.crayon-toolbar .crayon-button.crayon-nums-button .crayon-button-icon,.crayon-toolbar .crayon-button.crayon-nums-button:hover .crayon-button-icon,.crayon-toolbar .crayon-button.crayon-nums-button.crayon-pressed:hover .crayon-button-icon { background-position: 0 -32px }
.crayon-toolbar .crayon-button.crayon-plain-button .crayon-button-icon,.crayon-toolbar .crayon-button.crayon-plain-button:hover .crayon-button-icon,.crayon-toolbar .crayon-button.crayon-plain-button.crayon-pressed:hover .crayon-button-icon { background-position: 0 -48px }
.crayon-toolbar .crayon-button.crayon-mixed-button .crayon-button-icon,.crayon-toolbar .crayon-button.crayon-mixed-button:hover .crayon-button-icon,.crayon-toolbar .crayon-button.crayon-mixed-button.crayon-pressed:hover .crayon-button-icon { background-position: 0 -64px }
.crayon-toolbar .crayon-button.crayon-minimize .crayon-button-icon { background-position: 0 -80px; background-color: transparent !important }
.crayon-toolbar .crayon-button.crayon-expand-button .crayon-button-icon,.crayon-toolbar .crayon-button.crayon-expand-button:hover .crayon-button-icon,.crayon-toolbar .crayon-button.crayon-expand-button.crayon-pressed:hover .crayon-button-icon { background-position: 0 -96px }
.crayon-toolbar .crayon-button.crayon-wrap-button .crayon-button-icon,.crayon-toolbar .crayon-button.crayon-wrap-button:hover .crayon-button-icon,.crayon-toolbar .crayon-button.crayon-wrap-button.crayon-pressed:hover .crayon-button-icon { background-position: 0 -112px }
.crayon-toolbar .crayon-button.crayon-popup-button.crayon-pressed .crayon-button-icon,.crayon-toolbar .crayon-button.crayon-popup-button:active .crayon-button-icon,.crayon-toolbar .crayon-button.crayon-popup-button.crayon-pressed:active .crayon-button-icon { background-position: -24px 0 }
.crayon-toolbar .crayon-button.crayon-copy-button.crayon-pressed .crayon-button-icon,.crayon-toolbar .crayon-button.crayon-copy-button:active .crayon-button-icon,.crayon-toolbar .crayon-button.crayon-copy-button.crayon-pressed:active .crayon-button-icon { background-position: -24px -16px }
.crayon-toolbar .crayon-button.crayon-nums-button.crayon-pressed .crayon-button-icon,.crayon-toolbar .crayon-button.crayon-nums-button:active .crayon-button-icon,.crayon-toolbar .crayon-button.crayon-nums-button.crayon-pressed:active .crayon-button-icon { background-position: -24px -32px }
.crayon-toolbar .crayon-button.crayon-plain-button.crayon-pressed .crayon-button-icon,.crayon-toolbar .crayon-button.crayon-plain-button:active .crayon-button-icon,.crayon-toolbar .crayon-button.crayon-plain-button.crayon-pressed:active .crayon-button-icon { background-position: -24px -48px }
.crayon-toolbar .crayon-button.crayon-mixed-button.crayon-pressed .crayon-button-icon,.crayon-toolbar .crayon-button.crayon-mixed-button:active .crayon-button-icon,.crayon-toolbar .crayon-button.crayon-mixed-button.crayon-pressed:active .crayon-button-icon { background-position: -24px -64px }
.crayon-toolbar .crayon-button.crayon-minimize .crayon-button-icon { background-position: -24px -80px; background-color: transparent !important }
.crayon-toolbar .crayon-button.crayon-expand-button.crayon-pressed .crayon-button-icon,.crayon-toolbar .crayon-button.crayon-expand-button:active .crayon-button-icon,.crayon-toolbar .crayon-button.crayon-expand-button.crayon-pressed:active .crayon-button-icon { background-position: -24px -96px }
.crayon-toolbar .crayon-button.crayon-wrap-button.crayon-pressed .crayon-button-icon,.crayon-toolbar .crayon-button.crayon-wrap-button:active .crayon-button-icon,.crayon-toolbar .crayon-button.crayon-wrap-button.crayon-pressed:active .crayon-button-icon { background-position: -24px -112px }
.crayon-syntax .crayon-toolbar .crayon-language { padding-right: 8px !important }
.crayon-syntax .crayon-title,.crayon-syntax .crayon-language { float: left }
.crayon-main::-webkit-scrollbar,.crayon-plain::-webkit-scrollbar { height: 6px; overflow: visible; width: 6px; background: #EEE }
.crayon-main::-webkit-scrollbar-thumb,.crayon-plain::-webkit-scrollbar-thumb { background-color: #CCC; border: 1px solid #AAA; min-height: 8px; padding: 0; border-width: 1px }
.crayon-main::-webkit-scrollbar-button,.crayon-plain::-webkit-scrollbar-button { height: 0; width: 0; padding: 0 }
.crayon-main::-webkit-scrollbar-track,.crayon-plain::-webkit-scrollbar-track { border-width: 0 0 0 4px; border: 1px solid #BBB; border-right: 0; border-bottom: 0 }
.crayon-main::-webkit-scrollbar-corner,.crayon-plain::-webkit-scrollbar-corner { background: #EEE }
.crayon-main::-webkit-scrollbar-thumb:hover,.crayon-plain::-webkit-scrollbar-thumb:hover { background: #AAA; border: 1px solid #777 }
.crayon-syntax .crayon-pre,.crayon-syntax pre { color: #000; white-space: pre; margin: 0; padding: 0; overflow: visible; background: none !important; border: none !important }
.crayon-syntax .crayon-line { padding: 0 5px }
.crayon-syntax.crayon-wrapped .crayon-line { white-space: pre-wrap !important; height: auto }
.crayon-syntax-inline .crayon-pre,.crayon-syntax-inline pre { white-space: normal }
.crayon-syntax-inline-nowrap .crayon-pre,.crayon-syntax-inline-nowrap pre { white-space: pre }
.crayon-syntax { font-family: Monaco, "MonacoRegular", "Courier New", monospace; font-weight: 500 }
.crayon-syntax .crayon-toolbar *::selection,.crayon-syntax .crayon-nums *::selection { background: transparent }
.crayon-table .crayon-nums-content { white-space: nowrap }
.crayon-syntax .crayon-num,.crayon-syntax .crayon-pre .crayon-line,.crayon-syntax .crayon-toolbar *,.crayon-syntax .crayon-pre * { font-family: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; height: inherit }
.crayon-syntax .crayon-toolbar .crayon-button .crayon-button-icon { background-image: url("../images/toolbar/buttons.png"); height: 16px !important; width: 100%; position: absolute; left: 0; top: 50%; margin-top: -8px }
.crayon-syntax .crayon-toolbar .crayon-tools { position: absolute; right: 0 }
.crayon-syntax.crayon-expanded { position: absolute !important; margin: 0 !important }
.crayon-syntax.crayon-expanded .crayon-main { overflow: hidden !important }
.crayon-placeholder { width: 100% !important }
.crayon-toolbar-visible .crayon-toolbar { position: relative !important; margin-top: 0 !important; display: block !important }
.crayon-syntax.crayon-expanded .crayon-toolbar .crayon-tools { position: relative; right: auto; float: left !important }
.crayon-syntax .crayon-plain-wrap { height: auto !important; padding: 0 !important; margin: 0 !important }
.crayon-syntax .crayon-plain { width: 100%; height: 100%; position: absolute; opacity: 0; padding: 0 5px; margin: 0; border: 0; white-space: pre; overflow: auto; color: #000; background: #FFF }
.crayon-wrapped .crayon-plain { white-space: pre-wrap }
.bbp-body .crayon-syntax { clear: none !important }
.crayon-minimized .crayon-toolbar { cursor: pointer }
.crayon-minimized .crayon-plain-wrap,.crayon-minimized .crayon-main,.crayon-minimized .crayon-toolbar .crayon-tools * { display: none !important }
.crayon-minimized .crayon-toolbar .crayon-tools .crayon-minimize { display: block !important }
.crayon-minimized .crayon-toolbar { position: relative !important }
.crayon-syntax.crayon-minimized .crayon-toolbar { border-bottom: none !important }
.crayon-te *,#crayon-te-bar-content { font-family: "Lucida Grande", Arial, sans-serif !important; font-size: 12px }
.crayon-te input[type="text"],.crayon-te textarea { background: #f9f9f9; border: 1px solid #CCC; padding: 2px 4px; border-width: 1px; border-style: solid }
.crayon-te #crayon-code { font-family: monospace !important }
#crayon-te-content,#crayon-te-table { width: 100%; height: auto !important }
#crayon-range,#crayon-mark { width: 100px }
#crayon-te-table th,#crayon-te-table td { vertical-align: top; text-align: left }
.rtl #crayon-te-table th,.rtl #crayon-te-table td { text-align: right }
#crayon-te-table .crayon-tr-center td,#crayon-te-table .crayon-tr-center th { vertical-align: middle }
#crayon-te-table .crayon-nowrap { white-space: nowrap }
#crayon-te-bar { position: absolute; top: 0; left: 0; width: 100% }
#crayon-te-bar-content { border: 1px solid #666; border-bottom: 0; height: 26px; line-height: 25px; padding: 0 8px; padding-right: 0; background-color: #222; color: #cfcfcf }
#crayon-te-bar-content a { line-height: 25px; padding: 5px 10px; color: #DDD; font-weight: bold; text-decoration: none !important }
#crayon-te-bar-content a:hover { color: #FFF }
.crayon-te-seperator { color: #666; margin: 0; padding: 0 }
#crayon-te-bar-block { height: 34px; width: 100% }
#crayon-te-title { float: left }
#crayon-te-controls { float: right }
#crayon-url-th { vertical-align: top !important; padding-top: 5px }
.crayon-te-heading { font-size: 14px; font-weight: bold }
#crayon-te-settings-info { text-align: center }
.crayon-te-section { font-weight: bold; padding: 0 10px }
#crayon-te-sub-section { margin-left: 10px }
#crayon-te-sub-section .crayon-te-section { font-weight: normal; padding: 0 }
#crayon-code { height: 200px; white-space: pre }
#crayon-code,#crayon-url { width: 555px !important }
.crayon-disabled { background: #EEE !important }
.qt_crayon_highlight { background-image: linear-gradient(bottom,#daf2ff,white) !important }
.qt_crayon_highlight:hover { background: #ddebf2 !important }
.crayon-tag-editor-button-wrapper { display: inline-block }
.mce_crayon_tinymce { padding: 0 !important; margin: 2px 3px !important }
.mce-i-crayon_tinymce,.mce_crayon_tinymce { background: url("../images/crayon_tinymce.png") 0 0 !important }
a.mce_crayon_tinymce { background-position: 2px 0 !important }
.wp_themeSkin .mceButtonEnabled:hover span.mce_crayon_tinymce,.wp_themeSkin .mceButtonActive span.mce_crayon_tinymce { background-position: -20px 0 }
.wp_themeSkin span.mce_crayon_tinymce { background: none !important }
#crayon-te-table { margin-top: 26px; padding: 10px; border-collapse: separate !important; border-spacing: 2px !important }
#crayon-te-table th { width: 100px }
#crayon-te-clear { color: #666; background-color: #f4f4f4; border: 1px solid #CCC; margin-left: 8px }
#crayon-title { width: 360px }
#TB_window.crayon-te-ajax { overflow: auto !important }
#TB_window.crayon-te-ajax,#TB_window.crayon-te-ajax #TB_ajaxContent,#TB_window.crayon-te-ajax #TB_title { width: 680px !important }
#TB_window.crayon-te-ajax #TB_ajaxContent { padding: 0 !important; margin: 0 !important; width: 100% !important; height: auto !important; margin-top: 28px !important }
#TB_window.crayon-te-ajax #TB_title { position: fixed !important }
#TB_window.crayon-te-ajax #TB_title .crayon-te-submit { margin-top: 3px !important; float: right !important }
#TB_window.crayon-te-ajax a { color: #2587e2; text-decoration: none }
#TB_window.crayon-te-ajax a:hover { color: #499ce9 }
.crayon-te-quote { background: #DDD; padding: 0 2px }
#crayon-te-submit-wrapper { display: none }
#crayon-te-clear { display: none; margin: 0; margin-top: 10px }
.crayon-syntax-pre { background: red; white-space: pre; overflow: auto; display: block }
.crayon-question { padding: 1px 4px !important; text-decoration: none !important; color: #83b3cb !important; height: 15px !important; width: 15px !important }
.crayon-question:hover { background: #83b3cb !important; color: white !important; height: 15px !important; width: 15px !important }
.crayon-setting-changed,.crayon-setting-selected { background: #fffaad !important }
.crayon-question:hover { color: white; background: #a6d6ef }
#crayon-te-warning { display: none }
.crayon-te-info { padding: 5px !important; margin: 2px 0 !important }
#crayon-te-submit { margin-bottom: 5px }
.crayon-theme-github { margin-bottom: 25px !important; border: 1px solid #dedede !important; background-color: #f8f8ff !important; font-size: 100% !important; line-height: 130% !important }
.crayon-theme-github .crayon-toolbar { border-bottom: 1px solid #dedede !important; background-color: #eee !important }
.crayon-theme-github .crayon-toolbar .crayon-language,.crayon-theme-github .crayon-toolbar .crayon-title { font-size: 80% !important; color: #666 !important }
.crayon-theme-github .crayon-table .crayon-nums { background-color: #eee !important }
.crayon-theme-github .crayon-table .crayon-nums-content { padding-top: 5px !important; padding-bottom: 3px !important }
.crayon-theme-github .crayon-table .crayon-num { min-width: 1.2em !important; border-right: 1px solid #dedede !important; text-align: right !important; color: #aaa !important }
.crayon-theme-github .crayon-pre { padding-top: 5px !important; padding-bottom: 3px !important }
.crayon-theme-github .crayon-marked-line { background: #fffee2 !important }
.crayon-theme-github .crayon-marked-num { color: #1561ac !important; background: #b3d3f4 !important; border-width: 1px !important; border-color: #5999d9 !important }
.crayon-theme-github .crayon-pre .crayon-c { color: #999 !important; font-style: italic !important }
.crayon-theme-github .crayon-pre .crayon-s { color: #d14 !important }
.crayon-theme-github .crayon-pre .crayon-p { color: #b85c00 !important }
.crayon-theme-github .crayon-pre .crayon-ta { color: #FF0000 !important }
.crayon-theme-github .crayon-pre .crayon-k { color: teal !important }
.crayon-theme-github .crayon-pre .crayon-st { color: #000 !important; font-weight: bold !important }
.crayon-theme-github .crayon-pre .crayon-r { color: #000 !important; font-weight: bold !important }
.crayon-theme-github .crayon-pre .crayon-t { color: #800080 !important; font-weight: bold !important }
.crayon-theme-github .crayon-pre .crayon-m { color: #800080 !important }
.crayon-theme-github .crayon-pre .crayon-i { color: #000 !important }
.crayon-theme-github .crayon-pre .crayon-e { color: teal !important }
.crayon-theme-github .crayon-pre .crayon-v { color: #002D7A !important }
.crayon-theme-github .crayon-pre .crayon-cn { color: #099 !important }
.crayon-theme-github .crayon-pre .crayon-o { color: #006fe0 !important }
.crayon-theme-github .crayon-pre .crayon-sy { color: #333 !important }
.crayon-theme-github .crayon-pre .crayon-n { color: #666 !important; font-style: italic }
.crayon-theme-github .crayon-pre .crayon-f { color: #999 !important }
.crayon-theme-github .crayon-pre .crayon-h { color: #006fe0 !important }
.crayon-syntax .crayon-pre,.crayon-syntax pre { white-space: initial }
img { margin-top: 10px; margin-bottom: 10px }
img { margin-top: 10px; margin-bottom: 10px }

我们在上一篇介绍了JS Object的实现，这一篇将进一步介绍JS Array的实现。

在此之前，笔者将Chromium升级到了最新版本60，上一次是在元旦的时候下的57，而当前最新发布的稳定版本是57。57是三月上旬发布的，所以Chrome发布一个大版本至少用了两、三个月的时间。Chrome 60的devTool增加了很多有趣的功能，这里顺便提一下：

从Chrome源码看JS Array的实现

例如把没有用到的CSS/JS按比例标红，增加了全页的截屏功能，和一个本地代码的编辑器：

从Chrome源码看JS Array的实现

回到正文。

JS的Array是一个万能的数据结构，为什么这么说呢？因为首先它可以当作一个普通的数组来使用，即通过下标找到数组的元素：

普通数组
 
 
 
 
 
 

JavaScript

 
var array = [19, 50, 99];
console.log(array[0]);
1
2
vararray=[19,50,99];
console.log(array[0]);

然后它可以当作一个栈来使用，我们知道栈的特点是先进后出，栈的基本操作是出栈和入栈：

栈
 
 
 
 
 
 

JavaScript

 
var stack = [1, 2, 3];
stack.push(4); //入栈
var top = stack.pop(); //出栈
1
2
3
varstack=[1,2,3];
stack.push(4);          //入栈
vartop=stack.pop();  //出栈

同时它还可以当作一个队列，队列的特点是先进先出，基本操作是出队和入队：

队列
 
 
 
 
 
 

JavaScript

 
var queue = [1, 2, 3];
queue.push(4); //入队
var head = queue.shift(); //出队
1
2
3
varqueue=[1,2,3];
queue.push(4);             //入队
varhead=queue.shift();  //出队

甚至它还可以当作一个哈表表来使用：

哈希
 
 
 
 
 
 

JavaScript

 
var map = [];
map["id"] = 1234;
map["name"] = yin;
console.log(map["name"]);
1
2
3
4
varmap=[];
map["id"]=1234;
map["name"]=yin;
console.log(map["name"]);

另外，它还可以随时随地增删数组中任意位置的元素：

随时插入和删除元素
 
 
 
 
 
 

JavaScript

 
var array = [1, 2, 3, 4];
//从第3个元素开始，删掉1个元素，并插入-1，-2这两个元素
array.splice(2, 1, -1, -2);
//再来个2000的索引
array[2000] = 10;
1
2
3
4
5
vararray=[1,2,3,4];
//从第3个元素开始，删掉1个元素，并插入-1，-2这两个元素
array.splice(2,1,-1,-2);
//再来个2000的索引
array[2000]=10;

JS Array一方面提供了很大的便利，只要用一个数据结构就可以做很多事情，使用者不需要关心各者的区别，使得JS很容易入门。另一方面它屏蔽了数据结构的概念，不少写前端的都不知道什么是栈、队列、哈希、树，特别是那些不是学计算机，中途转过来的。然而这往往是不可取的。

另外一点是，即使是一些前端的老司机，他们也很难说清楚，这些数组函数操作的效率怎么样，例如说随意地往数组中间增加一个元素不会有性能问题么。所以就很有必要从源码的角度看一下数组是怎么实现的。

1. JS Array的实现

先看源码注释：

 
 
 
 
 
 

C++

 
// The JSArray describes JavaScript Arrays
// Such an array can be in one of two modes:
// - fast, backing storage is a FixedArray and length <= elements.length();
// Please note: push and pop can be used to grow and shrink the array.
// - slow, backing storage is a HashTable with numbers as keys.
class JSArray: public JSObject {
public:
// [length]: The length property.
DECL_ACCESSORS(length, Object)

// Number of element slots to pre-allocate for an empty array.
static const int kPreallocatedArrayElements = 4;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
// The JSArray describes JavaScript Arrays
//  Such an array can be in one of two modes:
//    - fast, backing storage is a FixedArray and length <= elements.length();
//       Please note: push and pop can be used to grow and shrink the array.
//    - slow, backing storage is a HashTable with numbers as keys.
classJSArray:publicJSObject{
public:
  // [length]: The length property.
  DECL_ACCESSORS(length,Object)
 
  // Number of element slots to pre-allocate for an empty array.
  staticconstintkPreallocatedArrayElements=4;
};

这里说明一下，如果不熟悉C/C++的，那把它成伪码就好了。

源码里面说了，JSArray有两种模式，一种是快速的，一种是慢速的，快速的用的是索引直接定位，慢速的使用用哈希查找，这个在上一篇《从Chrome源码看JS Object的实现》就已经提及，由于JSArray是继承于JSObject，所以它也是同样的处理方式，如下面的：

 
 
 
 
 
 

JavaScript

 
var array = [1, 2, 3]
array[2000] = 10;
1
2
vararray=[1,2,3]
array[2000]=10;

增加一个2000的索引时，array就会被转成慢元素。

如下的数组：

 
 
 
 
 
 

JavaScript

 
var a = [8, 1, 2];
1
vara=[8,1,2];

把a打印出来：

– map = 0x939ebe04359 [FastProperties]

– prototype = 0x27e86e126289

– elements = 0xe70c791d4e9 <FixedArray[3]> [FAST_SMI_ELEMENTS (COW)]

– length = 3

– properties = 0x2b609d202241 <FixedArray[0]> {

#length: 0x2019c3e58da9 <AccessorInfo> (const accessor descriptor)

}

– elements= 0xe70c791d4e9 <FixedArray[3]> {

0: 8

1: 1

2: 2

}

它有一个length的属性，它的elements有3个元素，按索引排列。当给它加一个2000的索引时：

 
 
 
 
 
 

JavaScript

 
var a = [8, 1, 2];
a[2000] = 10;
1
2
vara=[8,1,2];
a[2000]=10;

打印出来的array变成：

– map = 0x333c83f9dbb9 [FastProperties]

– prototype = 0xdcc53ba6289

– elements = 0x21a208a1d541 <FixedArray[29]> [DICTIONARY_ELEMENTS]

– length = 2001

– properties = 0x885d1402241 <FixedArray[0]> {

#length: 0x1f564a958da9 <AccessorInfo> (const accessor descriptor)

}

– elements= 0x21a208a1d541 <FixedArray[29]> {

2: 2 (data, dict_index: 0, attrs: [WEC])

0: 8 (data, dict_index: 0, attrs: [WEC])

2000: 10 (data, dict_index: 0, attrs: [WEC])

1: 1 (data, dict_index: 0, attrs: [WEC])

}

elements变成了一个慢元素哈希表，哈希表的容量为29。

由于快元素和慢元素上一节已经有详细讨论，这一节将不再重复。我们重点讨论数组的操作函数的实现。

2. Push和扩容

数组初始化大小为4：

 
 
 
 
 
 

C++

 
// Number of element slots to pre-allocate for an empty array.
static const int kPreallocatedArrayElements = 4;
1
2
  // Number of element slots to pre-allocate for an empty array.
  staticconstintkPreallocatedArrayElements=4;

执行push的时候会在数组的末尾添加新的元素，而一旦空间不足时，将进行扩容。

在源码里面push是用汇编实现的，在C++里面嵌入的汇编。这个应该是考虑到push是一个最为常用的操作，所以用汇编实现提高执行速度。在汇编的上面封装了一层，用C++调的封装的汇编的函数，在编译组装的时候，将把这些C++代码转成汇编代码。

计算新容量的函数：

 
 
 
 
 
 

C++

 
Node* CodeStubAssembler::CalculateNewElementsCapacity(Node* old_capacity,
ParameterMode mode) {
Node* half_old_capacity = WordOrSmiShr(old_capacity, 1, mode);
Node* new_capacity = IntPtrOrSmiAdd(half_old_capacity, old_capacity, mode);
Node* padding = IntPtrOrSmiConstant(16, mode);
return IntPtrOrSmiAdd(new_capacity, padding, mode);
}
1
2
3
4
5
6
7
Node*CodeStubAssembler::CalculateNewElementsCapacity(Node*old_capacity,
                                                      ParameterMode mode){
  Node*half_old_capacity=WordOrSmiShr(old_capacity,1,mode);
  Node*new_capacity=IntPtrOrSmiAdd(half_old_capacity,old_capacity,mode);
  Node*padding=IntPtrOrSmiConstant(16,mode);
  returnIntPtrOrSmiAdd(new_capacity,padding,mode);
}

如上代码新容量等于 ：

new_capacity = old_capacity /2 + old_capacity + 16

即老的容量的1.5倍加上16。初始化为4个，当push第5个的时候，容量将会变成：

new_capacity = 4 / 2 + 4 + 16 = 22

接着申请一块这么大的内存，把老的数据拷过去：

 
 
 
 
 
 

C++

 
Node* CodeStubAssembler::GrowElementsCapacity(
Node* object, Node* elements, Node* capacity, Node* new_capacity) {
// Allocate the new backing store.
Node* new_elements = AllocateFixedArray(new_capacity, mode);

// Copy the elements from the old elements store to the new.
CopyFixedArrayElements(elements, new_elements, capacity, new_capacity);
return new_elements;
}

1
2
3
4
5
6
7
8
9
Node*CodeStubAssembler::GrowElementsCapacity(
    Node*object,Node*elements,Node*capacity,Node*new_capacity){
  // Allocate the new backing store.
  Node*new_elements=AllocateFixedArray(new_capacity,mode);
 
  // Copy the elements from the old elements store to the new.
  CopyFixedArrayElements(elements,new_elements,capacity,new_capacity);
  returnnew_elements;
}

由于复制是用的memcopy，把整一段内存空间拷贝过去，所以这个操作还是比较快的。

再把新元素放到当前length的位置，再把length增加1：

 
 
 
 
 
 

C++

 
StoreFixedArrayElement(elements, var_length.value());
Increment(var_length, 1, mode);
1
2
StoreFixedArrayElement(elements,var_length.value());
Increment(var_length,1,mode);

可以来改点代码玩玩，我们知道push执行后的返回结果是新数组的长度，尝试把它改成返回老数组的长度：

 
 
 
 
 
 

C++

 
Node *old_length = LoadJSArrayLength(receiver);
Node *new_length = BuildAppendJSArray(/.../);
//args.PopAndReturn(new_length);
args.PopAndReturn(old_length);
1
2
3
4
Node*old_length=LoadJSArrayLength(receiver);
Node*new_length=BuildAppendJSArray(/.../);
//args.PopAndReturn(new_length);
args.PopAndReturn(old_length);

重新编译Chrome，在控制台上执行比较如下：

从Chrome源码看JS Array的实现

右边的新Chrome返回了4，左边正常的Chrome返回5.

3. Pop和减容

push是用汇编实现，而pop的逻辑是用C++写的。在执行pop的时候，第一步，获取到当前的length，用这个length – 1得到要删除的元素，然后调用setLength调整容量，最后返回删除的元素：

 
 
 
 
 
 

C++

 
int new_length = length - 1;
int remove_index = remove_position == AT_START ? 0 : new_length;
Handle<Object> result =
Subclass::GetImpl(isolate, *backing_store, remove_index);
Subclass::SetLengthImpl(isolate, receiver, new_length, backing_store);
return result;
1
2
3
4
5
6
intnew_length=length-1;
intremove_index=remove_position==AT_START?0:new_length;
Handle<Object>result=
    Subclass::GetImpl(isolate,*backing_store,remove_index);
Subclass::SetLengthImpl(isolate,receiver,new_length,backing_store);
returnresult;

我们重点看下这个减容的过程：

 
 
 
 
 
 

C++

 
if (2 * length <= capacity) {
// If more than half the elements won't be used, trim the array.
isolate->heap()->RightTrimFixedArray(*backing_store, capacity - length);
} else {
// Otherwise, fill the unused tail with holes.
BackingStore::cast(*backing_store)->FillWithHoles(length, old_length);
}
1
2
3
4
5
6
7
if(2*length<=capacity){
  // If more than half the elements won't be used, trim the array.
  isolate->heap()->RightTrimFixedArray(*backing_store,capacity-length);
}else{
  // Otherwise, fill the unused tail with holes.
  BackingStore::cast(*backing_store)->FillWithHoles(length,old_length);
}

如果容量大于等于length的2倍，则进行容量调整，否则用holes对象填充。第三行的rightTrim函数，会算出需要释放的空间大小，并做标记，并等待GC回收：

 
 
 
 
 
 

C++

 
int bytes_to_trim = elements_to_trim * element_size;
// Calculate location of new array end.
Address old_end = object->address() + object->Size();
Address new_end = old_end - bytes_to_trim;
CreateFillerObjectAt(new_end, bytes_to_trim, ClearRecordedSlots::kYes);
1
2
3
4
5
intbytes_to_trim=elements_to_trim*element_size;
// Calculate location of new array end.
Address old_end=object->address()+object->Size();
Address new_end=old_end-bytes_to_trim;
CreateFillerObjectAt(new_end,bytes_to_trim,ClearRecordedSlots::kYes);

也就是说，当数组的元素个数小于容量的一半时，就会进行减少的操作，将容量调整为实际的大小。

4. shift和splice数组中间的操作

push和pop都是在数组末尾操作，相对比较简单，而shfit、unshfit、splice是在数组的开始或者中间进行操纵。我们来看一下，如果是这种情况的又是如何调整数组元素的。

（1）shift是出队，即删除并返回数组的第一个元素。shift和pop调的都是同样的删除函数，只不过shift传的删除的postion是AT_STRT，源码里面会判断如果是AT_START的话，会把元素进行移动：

 
 
 
 
 
 

C++

 
if (remove_position == AT_START) {
Subclass::MoveElements(isolate, receiver, backing_store, 0, 1, new_length,
0, 0);
}
1
2
3
4
if(remove_position==AT_START){
    Subclass::MoveElements(isolate,receiver,backing_store,0,1,new_length,
                         0,0);
}

从1的位置移到0的位置，如上面第2行的第4、5个参数，这个move将会调leftTrim，和上面的rightTrim相反：

 
 
 
 
 
 

C++

 
*dst_elms.location() =
BackingStore::cast(heap->LeftTrimFixedArray(*dst_elms, src_index));
receiver->set_elements(*dst_elms);
1
2
3
*dst_elms.location()=
    BackingStore::cast(heap->LeftTrimFixedArray(*dst_elms,src_index));
receiver->set_elements(*dst_elms);

（2）unshfit在数组的开始位置插入元素，首先要判断容量是否足够存放，如果不够，将容量扩展为老容量的1.5倍加16，然后把老元素移到新的内存空间偏移为unshift元素个数的位置，也就是说要腾出起始的空间放unshfit传进来的元素，如果空间足够了，则直接执行memmove移动内存空间，最后再把unshif传进来的参数copy到开始的位置：

 
 
 
 
 
 

C++

 
int insertion_index = add_position == AT_START ? 0 : length;
// Copy the arguments to the start.
Subclass::CopyArguments(args, backing_store, add_size, 1, insertion_index);
// Set the length.
receiver->set_length(Smi::FromInt(new_length));
1
2
3
4
5
intinsertion_index=add_position==AT_START?0:length;
// Copy the arguments to the start.
Subclass::CopyArguments(args,backing_store,add_size,1,insertion_index);
// Set the length.
receiver->set_length(Smi::FromInt(new_length));

并更新array的length。

（3）splice的操作已经几乎不用去看源码了，通过shift和unshift的操作是怎么样的，就可以想象到它的执行过程是怎样的，只是shift/unshfit操作的index是0，而splice可以指定index。具体代码如下：

 
 
 
 
 
 

C++

 
// Delete and move elements to make space for add_count new elements.
if (add_count < delete_count) {
Subclass::SpliceShrinkStep(isolate, receiver, backing_store, start,
delete_count, add_count, length, new_length);
} else if (add_count > delete_count) {
backing_store =
Subclass::SpliceGrowStep(isolate, receiver, backing_store, start,
delete_count, add_count, length, new_length);
}

// Copy over the arguments.
Subclass::CopyArguments(args, backing_store, add_count, 3, start);

1
2
3
4
5
6
7
8
9
10
11
12
// Delete and move elements to make space for add_count new elements.
if(add_count<delete_count){
  Subclass::SpliceShrinkStep(isolate,receiver,backing_store,start,
                             delete_count,add_count,length,new_length);
}elseif(add_count>delete_count){
  backing_store=
      Subclass::SpliceGrowStep(isolate,receiver,backing_store,start,
                               delete_count,add_count,length,new_length);
}
 
// Copy over the arguments.
Subclass::CopyArguments(args,backing_store,add_count,3,start);

它需要先shrink或者grow中间元素的空间，以适应增加元素比删除元素少或者多的情况，然后进行容量调整和移动元素。

接着再来看下两个“小清新”的函数

5. Join和Sort

说它们是小清新，是因为它们是用JS实现的，然后再用wasm打包成native code。不过，join的实现逻辑并不简单，因为array的元素本身具有多样化，可能为慢元素或者快元素，还可能带有循环引用，对于慢元素，需要先排下序：

 
 
 
 
 
 

C++

 
var keys = GetSortedArrayKeys(array, %GetArrayKeys(array, length));
1
varkeys=GetSortedArrayKeys(array,%GetArrayKeys(array,length));

预处理完之后，最后创建一个字符串数组，用连接符连起来：

 
 
 
 
 
 

JavaScript

 
// Construct an array for the elements.
var elements = new InternalArray(length);
for (var i = 0; i < length; i++) {
elements[i] = ConvertToString(use_locale, array[i]);
}

if (separator === '') {
return %StringBuilderConcat(elements, length, '');
} else {
return %StringBuilderJoin(elements, length, separator);
}

1
2
3
4
5
6
7
8
9
10
11
// Construct an array for the elements.
varelements=newInternalArray(length);
for(vari=0;i<length;i++){
  elements[i]=ConvertToString(use_locale,array[i]);
}
 
if(separator===''){
  return%StringBuilderConcat(elements,length,'');
}else{
  return%StringBuilderJoin(elements,length,separator);
}

而sort函数是用的快速排序：

 
 
 
 
 
 

JavaScript

 
function ArraySort(comparefn) {
CHECK_OBJECT_COERCIBLE(this, "Array.prototype.sort");
%Log("js/array.js execute ArraySort"); //手动添加的log打印，确保执行的是这里

var array = TO_OBJECT(this);
var length = TO_LENGTH(array.length);
return InnerArraySort(array, length, comparefn);
}

1
2
3
4
5
6
7
8
functionArraySort(comparefn){
  CHECK_OBJECT_COERCIBLE(this,"Array.prototype.sort");
  %Log("js/array.js execute ArraySort");  //手动添加的log打印，确保执行的是这里
 
  vararray=TO_OBJECT(this);
  varlength=TO_LENGTH(array.length);
  returnInnerArraySort(array,length,comparefn);
}

当数组元素的个数不超过10个时，是用的插入排序：

 
 
 
 
 
 

JavaScript

 
function InnerArraySort(array, length, comparefn) {
// In-place QuickSort algorithm.
// For short (length <= 10) arrays, insertion sort is used for efficiency.
function QuickSort(a, from, to) {
var third_index = 0;
while (true) {
// Insertion sort is faster for short arrays.
if (to - from <= 10) {
InsertionSort(a, from, to);
return;
}
//other code ...
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
functionInnerArraySort(array,length,comparefn){
  // In-place QuickSort algorithm.
  // For short (length <= 10) arrays, insertion sort is used for efficiency.
  functionQuickSort(a,from,to){
    varthird_index=0;
    while(true){
      // Insertion sort is faster for short arrays.
      if(to-from<=10){
        InsertionSort(a,from,to);
        return;
      }
      //other code ...
    }
  }
}

快速排序算法里面有一个比较重要的地方是选择枢纽元素，最简单的是每次都是选取第一个元素，或者中间的元素，在源码里面是这样选择的：

 
 
 
 
 
 

JavaScript

 
if (to - from > 1000) {
third_index = GetThirdIndex(a, from, to);
} else {
third_index = from + ((to - from) >> 1);
}
1
2
3
4
5
if(to-from>1000){
  third_index=GetThirdIndex(a,from,to);
}else{
  third_index=from+((to-from)>>1);
}

如果元素个数在1000以内，则使用它们的中间元素，否则要算一下， 这个算法比较有趣：

 
 
 
 
 
 

JavaScript

 
function GetThirdIndex(a, from, to) {
var t_array = new InternalArray();
// Use both 'from' and 'to' to determine the pivot candidates.
var increment = 200 + ((to - from) & 15);
var j = 0;
from += 1;
to -= 1;
for (var i = from; i < to; i += increment) {
t_array[j] = [i, a[i]];
j++;
}
t_array.sort(function(a, b) {
return comparefn(a[1], b[1]);
});
var third_index = t_array[t_array.length >> 1][0];
return third_index;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
functionGetThirdIndex(a,from,to){
  vart_array=newInternalArray();
  // Use both 'from' and 'to' to determine the pivot candidates.
  varincrement=200+((to-from)&15);
  varj=0;
  from+=1;
  to-=1;
  for(vari=from;i<to;i+=increment){
    t_array[j]=[i,a[i]];
    j++;
  }
  t_array.sort(function(a,b){
    returncomparefn(a[1],b[1]);
  });
  varthird_index=t_array[t_array.length>>1][0];
  returnthird_index;
}

先取一个递增间距200~215之间，再循环取出原元素里面落到这个间距的元素，放到一个新的数组里面（这个数组是C++里面的数组），然后排下序，取中间的元素。因为枢纽元素的刚好是所有元素的中位数时，排序的效果最好，而这里是取出少数元素的中位数，类似于抽样模拟，缺点是它得再借助另外的排序算法。

最后再比较一下Array和线性链接的速度。

6. Array和线性链接的速度

线性链接是一种非连续存储的数据结构，每个元素都有一个指针指向它的下一个元素，所以它删除元素的时候不需要移动其它元素，也不需要考虑扩容的事情，但是它的查找比较慢。我们实现一个简单的List和Array进行比较。

List的每个节点用一个Node表示：

 
 
 
 
 
 

JavaScript

 
class Node{
constructor(value, next){
this.value = value;
this.next = next;
}
}
1
2
3
4
5
6
classNode{
    constructor(value,next){
        this.value=value;
        this.next=next;
    }
}

每个List都有一个头指针指向第一个元素，和一个length记录它的长度：

 
 
 
 
 
 

JavaScript

 
class List{
constructor(){
this.head = null;
this.tail = null;
this.length = 0;
}
}
1
2
3
4
5
6
7
classList{
    constructor(){
        this.head=null;
        this.tail=null;
        this.length=0;
    }
}

然后实现它的push和unshift函数：

 
 
 
 
 
 

C++

 
class List{
unshift(value){
return this.insert(0, value);
}
push(value){
if(this.head === null){
this.head = new Node(value, this.tail);
this.length++;
} else {
this.insert(this.length, value);
}
return this.length;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
classList{
    unshift(value){
        returnthis.insert(0,value);
    }
    push(value){
        if(this.head===null){
            this.head=newNode(value,this.tail);
            this.length++;
        }else{
            this.insert(this.length,value);
        }
        returnthis.length;
    }
}

两个函数都会调一个通用的insert函数：

 
 
 
 
 
 

JavaScript

 
insert(index, value){
var insertPos = this.head;
//找到需要插入的位置的节点
for(var i = 0; i < index - 1; i++){
insertPos = insertPos.next;
}
var node = null;
if(index === 0){
node = new Node(value, this.head);
this.head = node;
} else {
node = new Node(value, insertPos.next);
insertPos.next = node;
}
this.length++;
return value;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
insert(index,value){
    varinsertPos=this.head;
    //找到需要插入的位置的节点
    for(vari=0;i<index-1;i++){
        insertPos=insertPos.next;
    }
    varnode=null;
    if(index===0){
        node=newNode(value,this.head);
        this.head=node;
    }else{
        node=newNode(value,insertPos.next);
        insertPos.next=node;
    }
    this.length++;
    returnvalue;
}

有了这个List之后，就可以初始化一个list和array：

 
 
 
 
 
 

JavaScript

 
var list = new List();
var arr = [];
for(var i = 0; i < 100; i++){
list.push(i);
arr.push(i);
}
1
2
3
4
5
6
varlist=newList();
vararr=[];
for(vari=0;i<100;i++){
    list.push(i);
    arr.push(i);
}

可以来比较这个List和Array的存储方式，非连续和连续的区别：

从Chrome源码看JS Array的实现

然后用下面的代码比较List和Array入队操作的时间：

 
 
 
 
 
 

JavaScript

 
var count = 10000;
console.time("list unshfit");
for(var i = 0; i < count; i++){
list.unshift(i);
}
console.timeEnd("list unshfit");

console.time("array unshfit");
for(var i = 0; i < count; i++){
arr.unshift(i);
}
console.timeEnd("array unshfit");

1
2
3
4
5
6
7
8
9
10
11
12
varcount=10000;
console.time("list unshfit");
for(vari=0;i<count;i++){
    list.unshift(i);
}
console.timeEnd("list unshfit");
 
console.time("array unshfit");
for(vari=0;i<count;i++){
    arr.unshift(i);
}
console.timeEnd("array unshfit");

再比较从正中间位置插入元素的时间：

 
 
 
 
 
 

CoffeeScript

 
console.time("list insert middle with index");
for(var i = 0; i < count; i++){
insertPos = list.insert(list.length >> 1, i);
}
console.timeEnd("list insert middle with index");

console.time("array insert middle");
for(var i = 0; i < count; i++){
arr.splice(arr.length >> 1, 0, i);
}
console.timeEnd("array insert middle");

1
2
3
4
5
6
7
8
9
10
11
console.time("list insert middle with index");
for(vari=0;i<count;i++){
    insertPos=list.insert(list.length>>1,i);
}
console.timeEnd("list insert middle with index");
 
console.time("array insert middle");
for(vari=0;i<count;i++){
    arr.splice(arr.length>>1,0,i);
}
console.timeEnd("array insert middle");

运行可以得到以下表格：

从Chrome源码看JS Array的实现

可以看到在队首插入元素，使用线性链接List的时间将会数量级的优于Array。如果是在中间位置插入的话，由于 List的查找花费了很多时间，导致总时间明显高于Array。但是如果在插入的时候，记住上一次的位置，那么List又会明显快于Array。如下换成记录插入的位置：

 
 
 
 
 
 

JavaScript

 
console.time("list insert middle with pos");
var insertPos = list.getNode(list.length >> 1);
for(var i = 0; i < count; i++){
insertPos = list.insertFromNode(insertPos, i);
}
console.timeEnd("list insert middle with pos");
1
2
3
4
5
6
console.time("list insert middle with pos");
varinsertPos=list.getNode(list.length>>1);
for(vari=0;i<count;i++){
    insertPos=list.insertFromNode(insertPos,i);
}
console.timeEnd("list insert middle with pos");

时间比较List又快于Array：

从Chrome源码看JS Array的实现

综上，本文介绍了JS Array的实现，特别是它的操作函数，分析了它是怎么调整容量和移动元素的，并用了一个线性链接进行比较。Array的实现用了三种语言：汇编、C++和JS，最常用的如push用了汇编实现，比较常用的如pop/splice等用了C++，较为少用的如join/sort用了JS。

Array为快元素即普通的数组时，增删元素操作需要不断的扩容、减容和调整元素的位置。特别是当不断地在起始位置插入元素时，即当作一个队列来使用，和链表相比，这种时间效率还是比较低下的。如果使用的场景是要根据index删除元素，使用Array还是有优势，但是若能够很快定位到删除元素的位置，链表毫无疑问是更合适的。

相关阅读：

  1. 从Chrome源码看浏览器如何构建DOM树
  2. 从Chrome源码看浏览器的事件机制
  3. 从Chrome源码看浏览器如何计算CSS
  4. 从Chrome源码看浏览器如何layout布局
  5. 从Chrome源码看JS Object的实现
Post Views: 1

从Chrome源码看JS Array的实现的更多相关文章

  1. 从Chrome源码看浏览器的事件机制

    .aligncenter { clear: both; display: block; margin-left: auto; margin-right: auto } .crayon-line spa ...

  2. 从Chrome源码看audio&sol;video流媒体实现二（转）

    第一篇主要介绍了Chrome加载音视频的缓冲控制机制和编解码基础,本篇将比较深入地介绍解码播放的过程.以Chromium 69版本做研究. 由于Chromium默认不能播放Mp4,所以需要需要改一下源 ...

  3. 从Chrome源码看浏览器如何构建DOM树

    .aligncenter { clear: both; display: block; margin-left: auto; margin-right: auto } p { font-size: 1 ...

  4. 从Chrome源码看audio&sol;video流媒体实现一（转）

    现在绝大多数的网站已经从flash播放器转向了浏览器原生的audio/video播放器,浏览器是如何加载和解析多媒体资源的,这对于web开发者来说是一个黑盒,所以很有必要看一下浏览器是怎么实现的,Ch ...

  5. 观V8源码中的array&period;js，解析 Array&period;prototype&period;slice为什么能将类数组对象转为真正的数组？

    在官方的解释中,如[mdn] The slice() method returns a shallow copy of a portion of an array into a new array o ...

  6. 从微信小程序开发者工具源码看实现原理（四）- - 自适应布局

    从前面从微信小程序开发者工具源码看实现原理(一)- - 小程序架构设计可以知道,小程序大部分是通过web技术进行渲染的,也就是最终通过浏览器的dom tree + cssom来生成渲染树:既然最终是通 ...

  7. 从微信小程序开发者工具源码看实现原理（一）- - 小程序架构设计

    使用微信小程序开发已经很长时间了,对小程序开发已经相当熟练了:但是作为一名对技术有追求的前端开发,仅仅熟练掌握小程序的开发感觉还是不够的,我们应该更进一步的去理解其背后实现的原理以及对应的考量,这可能 ...

  8. 从源码看Azkaban作业流下发过程

    上一篇零散地罗列了看源码时记录的一些类的信息,这篇完整介绍一个作业流在Azkaban中的执行过程,希望可以帮助刚刚接手Azkaban相关工作的开发.测试. 一.Azkaban简介 Azkaban作为开 ...

  9. Google Chrome 源码下载地址 &lpar;Google Chrome Source Code Download&rpar;

    1. Google Chrome 源码 SVN 地址:http://src.chromium.org/svn.包含有 Chrome.Gears.Webkit.GCC 等源码以及编译依赖工具.Chrom ...

随机推荐

  1. ADF&lowbar;Controller系列4&lowbar;通过创建ADF Menu作为页面向导（Part2）

    2015-02-15 Created By BaoXinjian

  2. Android IOS WebRTC 音视频开发总结（四三）-- 诚信交易案例分享

    本文主要记录一些诚信交易的案例(两个陌生人之间没有合同,没有订金,没有讨价还价,完全靠诚信完成的交易), 特别纪录下来并不是因为金额有多高,而是因为在现在这种社会要完成这样的交易太难,特别是像咨询这种 ...

  3. Java 图片提取RGB数组 RGBOfCharMaps &lpar;整理&rpar;

    package demo; /** * Java 图片提取RGB数组 RGBOfCharMaps (整理) * 声明: * 和ImageCombining配合使用的工具,这里是提取图片的R.G.B生成 ...

  4. CSS的总结&lpar;选择器&comma;伪类等&period;&period;&period;&rpar;

    关于组合选择器可参考:http://www.cnblogs.com/starof/p/4453458.html 主要内容 CSS概述 CSS和HTML结合的四种方式 CSS样式优先级和代码规范 CSS ...

  5. nginx 配置 rewrite 跳转

    在访问 test.com 网站时,会自动跳转到 www.test.com ,这是因为该网站做了 URL rewrite 重定向,一般网页重定向跳转分为两种,301 和 302 :301,302 都是H ...

  6. IaaS，PaaS，SaaS 的区别&lpar;转&rpar;

    越来越多的软件,开始采用云服务. 云服务只是一个统称,可以分成三大类. IaaS:基础设施服务,Infrastructure-as-a-service PaaS:平台服务,Platform-as-a- ...

  7. CentOS7&period;0小随笔——指令基本操作（Part&period;A）

    与其说是CentOS7.0的小随笔,说老实话,基本指令在每个发行版本的Linux中都基本上是一致的. Part.A部分我们讲述以下四个方面:命令行界面与图形界面.Linux系统的关闭与重启.命令行帮助 ...

  8. &lbrack;T-ARA&rsqb;&lbrack;결혼 하지마&rsqb;&lbrack;不要结婚&rsqb;

    歌词来源:http://music.163.com/#/song?id=27808773 作曲 : 二段横踢 [作曲 : 二段横踢] 作词 : 二段横踢 [作词 : 二段横踢] Hey anybody ...

  9. luogu P1663 山

    题目链接 luogu P1663 山 题解 只需要求出下凸包的最低点就好了 显然是由两个斜率相反的直线相交来的 盼下最低点为直线的情况 代码 #include<cstdio> #inclu ...

  10. 关于 TRegEx&period;Split&lpar;&rpar;

    表达式中的括号将严重影响分割结果. uses RegularExpressions; const FSourceText = '1: AAA 2: BBB 3: CCC'; // 分隔符将有三部分构成 ...

相关文章